LC1094.拼车

思路

• 思路非常自然，类似于真实情况的模拟。差分的本质，就是在模拟上车下车情景。
• 差分的一大作用是减少重复操作
• diff[from] += passengers表示上车
• 上车之后人数一直不变，diff[from + 1] ...统统为0，代表车上的人数没有变化
• diff[to] -= passengers表示下车
• 对差分数组求和，也得到了当前时刻车上的总人数

代码

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> diff(1000 + 5, 0);
        int n_trips = trips.size();
        for (int i = 0; i < n_trips; ++i) {
            int passengers = trips[i][0];
            int from = trips[i][1];
            int to = trips[i][2];
            diff[from] += passengers;
            diff[to] -= passengers;
        }
        int cur_sum = 0;
        for (int i = 0; i < 1001; i++) {
            cur_sum += diff[i];
            if (cur_sum > capacity) {
                return false;
            }
        }
        return true;
    }
};