1094. 拼车

Difficulty
Medium
Tags
差分
扫描线
URL
https://leetcode-cn.com/problems/car-pooling/
Star
假设你是一位顺风车司机，车上最初有 capacity 个空座位可以用来载客。由于道路的限制，车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向，你可以将其想象为一个向量）。
这儿有一份乘客行程计划表 trips[][]，其中 trips[i] = [num_passengers, start_location, end_location] 包含了第 i 组乘客的行程信息：
  • 必须接送的乘客数量；
  • 乘客的上车地点；
  • 以及乘客的下车地点。
这些给出的地点位置是从你的 初始 出发位置向前行驶到这些地点所需的距离（它们一定在你的行驶方向上）。
请你根据给出的行程计划表和车子的座位数，来判断你的车是否可以顺利完成接送所有乘客的任务（当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false）。
示例 1：
输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false
示例 2：
输入：trips = [[2,1,5],[3,3,7]], capacity = 5
输出：true
示例 3：
输入：trips = [[2,1,5],[3,5,7]], capacity = 3
输出：true
示例 4：
输入：trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
输出：true
提示：
  • 你可以假设乘客会自觉遵守 “先下后上” 的良好素质
  • trips.length <= 1000
  • trips[i].length == 3
  • 1 <= trips[i][0] <= 100
  • 0 <= trips[i][1] < trips[i][2] <= 1000
  • 1 <= capacity <= 100000
通过次数36,854提交次数64,177

法1 扫描线

思路
经典的会议室题目，只不过会议室是每次加1，本题是每次上车的人数，不是+1
题解
class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        if len(trips) == 1:
            return trips[0][0] <= capacity

        # 起点 + val
        # 终点 -val
        points = []
        for trip in trips:
            t_1 = [trip[1], trip[0]]
            t_2 = [trip[2], -trip[0]]
            points.append(t_1[:])
            points.append(t_2[:])

        points.sort()

        count = 0
        for p in points:
            count += p[1]
            if count > capacity:
                return False

        return True

差分数组

思路
根据题目用数组构建每一段完整的人数，数组下标为时间，数组值为人数。然后采用差分数组来优化上下车的时候对数组的操作。
题解
class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        diff = [0] * 1001
        
        # 顺便纪律max_time
        max_t = 0
        for trip in trips:
            diff[trip[1]] += trip[0]
            diff[trip[2]] -= trip[0]
            max_t = max(max_t, trip[1], trip[2])
        
        # print(diff)
        count = 0
        for i in range(0, max_t+1):
            count += diff[i]
            if count > capacity:
                return False

        return True