Problem: 1094. 拼车
补一个Python版本
相当于在一条路上开车,乘客在某个时间点上车,他们会影响在下车之前的路程的车载人数。
很明显这是差分的做法,只要把行车的路程抽象成一个差分数组,把上下车抽象成区间更改,一切都变得简单
Code
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
road = [0] * 1010
for num, from_, to in trips:
road[from_] += num
road[to] -= num
sum_ = 0
# 对于差分数组来说,还原过程就是:i从1开始,不断进行road[i] += road[i - 1]
# 我们需要检测每一个点还原后的值是否大于capacity,
# 其实就是将整个road数组累加起来,检测累加过程是否大于capacity
for e in road:
sum_ += e
if sum_ > capacity:
return False
return True