Problem: 1094. 拼车

Code

/*
相当于在一条路上开车，乘客在某个时间点上车，他们会影响在下车之前的路程的车载人数。很明显这是差分的做法。*/
class Solution {
public:bool carPooling(vector<vector<int>>& trips, int capacity) {vector<int> road(1010, 0);for (auto &v : trips) {int num = v[0], from = v[1], to = v[2];// 差分，将该批次的人数加入到差分数组中road[from] += num; // 上车人数road[to] -= num; // 下车人数// 如果该批次就大于capacity了，说明直接为falseif (road[from] >capacity) return false;}// 重构数组，考虑多个上车批次的影响for (int i = 0; i < 1001; i++) {road[i] += i - 1 >= 0 ? road[i - 1] : 0;if (road[i] > capacity) return false;}return true;}
};