1094.拼车.md

1094.拼车

https://leetcode-cn.com/problems/car-pooling/

差分数组

根据题目序列，统计所有时刻的车上乘客数，若某时刻乘客数超过最大容量则返回false

class Solution:
    def carPooling(self, trips, capacity) -> bool:
        # 计算差分
        diff = [0] * 1001
        for trip in trips:
            val = trip[0]
            i = trip[1]
            j = trip[2]
            diff[i] += val
            if j+1 < 1000:
                diff[j] -= val
        # 还原数组
        count = [0] * 1001
        count[0] = diff[0]
        for i in range(1001):
            if i == 0:
                count[i] = diff[0]
            else:
                count[i] = count[i-1] + diff[i]
            if count[i] > capacity:
                return False
        return True