Description

假设你是一位顺风车司机，车上最初有 capacity 个空座位可以用来载客。由于道路的限制，车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向，你可以将其想象为一个向量）。

这儿有一份乘客行程计划表 trips[][]，其中 trips[i] = [num_passengers, start_location, end_location] 包含了第 i 组乘客的行程信息：

• 必须接送的乘客数量；
• 乘客的上车地点；
• 以及乘客的下车地点。

这些给出的地点位置是从你的 初始 出发位置向前行驶到这些地点所需的距离（它们一定在你的行驶方向上）。

请你根据给出的行程计划表和车子的座位数，来判断你的车是否可以顺利完成接送所有乘客的任务（当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false）。

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

CODE

这里最重要的是理解上车地点

class Solution5:
    def carPooling(self, trips, capacity):
        tmp = [0 for _ in range(1000)]

        #构造差分数组
        for add,m,n in trips:
            # 对应list的值
            # m -= 1
            # n -= 1
            # 题中这里的m是可以为0的
            print('---------------------------------------')
            if m > 0:
                tmp[m] += add
            elif m == 0:
                tmp[0] = add

            if n < 1000:
                # tmp[n + 1] -= add
                # 这里为n的原因是,客户虽然是到第n站，
                # 但第n站先下车就不会占座
                tmp[n] -= add
            print(tmp)
            print('---------------------------')

        if(tmp[0] > capacity):
            return False

        # get结果
        for k in range(1,1000):
            tmp[k] += tmp[k - 1]
            if (tmp[k] > capacity):
                return  False
        print(tmp)
        return True

S5 = Solution5()
# trips = [[2,1,5],[3,3,7]]
trips = [[2,1,5],[3,5,7]]
# trips = [[9,0,1],[3,3,7]]
# capacity = 5
capacity = 3
print(S5.carPooling(trips,capacity))