筆記：【演算法新手村】[初階]筆記06 - 差分(一維)

題目翻譯

有一輛車，車內共有 capacity 個空座位。這輛車只會向東行駛（也就是說，它不能掉頭向西開）。
給定一個整數 capacity 和一個陣列 trips，其中 trips[i] = [numPassengersᵢ, fromᵢ, toᵢ] 代表第 i 趟行程有 numPassengersᵢ 位乘客，且接送他們的地點分別為 fromᵢ（上車地點）與 toᵢ（下車地點）。地點是以車輛初始位置向東行駛的公里數來表示。如果可以順利接送所有行程中的乘客且不超過載客量，請回傳 true，否則回傳 false。

解題思路

這題的關鍵在於：乘客在 toᵢ 就已經下車了，所以他們不會佔用從 toᵢ 到之後路段的座位。
所以我們只需要記錄變動點(不需要模擬每一公里的狀態)，只需要關注有人上車或下車的地點。

在 fromᵢ 地點，座位需求增加 numPassengersᵢ
在 toᵢ 地點，座位需求減少 numPassengersᵢ

最後檢查載客量：按照地點順序加總這些變動(做前綴和)。如果在任何一個時間點，總乘客數超過了 capacity，就代表失敗。

在做這類型的題目時，可以直接把陣列開的較大一些，這樣可以使用索引1作為開頭，我這邊選的是N = 1010，理論上1001就已經足夠。

程式碼實作 (C++)

#define N 1010
class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        int n = trips.size();
        int Max = 0;
        vector<int> d(N);
        
        for(int i = 0 ; i < n ; i++){
            int k = trips[i][0];
            int l = trips[i][1];
            int r = trips[i][2];
            
            d[l] += k;
            d[r] -= k;
        }
        
        bool ans = true;
        int nowPassenger = 0;
        
        for(int& x : d){
            nowPassenger += x;
            
            if(nowPassenger > capacity){
                ans = false;
                break;
            }
        }

        return ans;
    }
};