Problem: 1094. 拼车
相当于在一条路上开车,乘客在某个时间点上车,他们会影响在下车之前的路程的车载人数。
很明显这是差分的做法,只要把行车的路程抽象成一个差分数组,把上下车抽象成区间更改,一切都变得简单
Code
/**
* @param {number[][]} trips
* @param {number} capacity
* @return {boolean}
*/
var carPooling = function(trips, capacity) {
const road = new Array(1010).fill(0);
for (const [num, from, to] of trips) {
road[from] += num;
road[to] -= num;
}
// 对于差分数组来说,还原过程就是:i从1开始,不断进行road[i] += road[i - 1]
// 我们需要检测每一个点还原后的值是否大于capacity,
// 其实就是将整个road数组累加起来,检测累加过程是否大于capacity
let sum = 0;
for (const v of road) {
sum += v;
if (sum > capacity) {
return false;
}
}
return true;
};