Skip to main content

1094. 拼车

1094. 拼车​

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

假设你是一位顺风车司机，车上最初有 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

通过次数8,769 | 提交次数14,994

Second Try​

2020-06-28

搞个加速版本，只需要记录上下车点就行了，不需要在这个过程中对每个位置进行修改。区别在于这个需要两轮迭代，初看起来还以为花费更多时间。

又是一个双百版本，不错不错，参考评论来的方法论。

class Solution(object):
    def carPooling(self, trips, capacity):
        """
        :type trips: List[List[int]]
        :type capacity: int
        :rtype: bool
        """
        # 又是一个双百版本，不错不错，参考评论来的方法论
        # 搞个加速版本，只需要记录上下车点就行了，不需要在这个过程中对每个位置进行修改
        max_trip = max(trips, key = lambda x: x[2])[2]
        # 一轮循环一波过，还不需要对trips进行排序
        capacity_change = [0 for i in range(max_trip + 1)]
        for (p, s, e) in trips:
            capacity_change[s] -= p
            capacity_change[e] += p
        for cc in capacity_change:
            capacity += cc
            if capacity < 0:
                return False
        return True
  • 执行用时：40 ms, 在所有 Python 提交中击败了100.00%的用户
  • 内存消耗：12.9 MB, 在所有 Python 提交中击败了100.00%的用户

First Try​

2020-06-28

除了空间占用量比较大，好像也没什么缺点了？就是非常形象的曲线画图的方式，遇到占用的往下减就行了。一眼看上去又以为动态规划，结果其实就是一路往前怼就行了。

class Solution(object):
    def carPooling(self, trips, capacity):
        """
        :type trips: List[List[int]]
        :type capacity: int
        :rtype: bool
        """

        # 没有什么动态规划的内容，就是一路遇到谁就带上，好像没什么难度？
        # 还是遇到bug了，测试案例没做完就直接上传 [[2,1,5],[3,5,7]] 3
        # 重点在于下车那一站是不占用空间的。。
        trips = sorted(trips, key=lambda x: x[1])
        max_trip = max(trips, key=lambda x: x[2])[2]
        exhaused = [capacity for i in range(max_trip + 1)]
        while len(trips):
            p, s, e = trips.pop(0)
            for i in range(s, e):
                exhaused[i] -= p
                if exhaused[i] < 0:
                    return False
        return True
  • 执行用时：164 ms, 在所有 Python 提交中击败了27.14%的用户
  • 内存消耗：13 MB, 在所有 Python 提交中击败了100.00%的用户