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了,说明直接为false
if (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;
}
};