这种连续区间的加法处理,是典型的差分数组优化。
class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
vector<int> delta(1010);
for(auto trip: trips){
delta[trip[1]] += trip[0];
delta[trip[2]] -= trip[0];
}
int cur = 0;
for(int i = 0; i <= 1000; i++){
cur += delta[i];
if(cur > capacity){
return false;
}
}
return true;
}
};