Python程序检查是否可以接送给定列表中的所有乘客

假设我们有一个名为requested_trips的矩阵，其中每一行包含[start_x, end_x, num_passengers]，我们还有一个capacity值。现在每个请求的行程都要求在start_x接送num_passengers名乘客，并在end_x放下他们。我们还有一辆汽车，其容量为给定值，并从位置x = 0开始。我们希望接送所有乘客，并且只能向右移动，我们需要检查是否可以接送所有人。

因此，如果输入类似于trips = [[1, 25, 2], [3, 4, 3],[5, 12, 3]] capacity = 6，则输出将为True

为了解决这个问题，我们将遵循以下步骤：

• events := 一个新的列表

• 对于trips中的每个集合(sx, ex, np)，执行以下操作

  • 将(sx, np)对插入到events的末尾

  • 将(ex, -np)对插入到events的末尾

• carrying := 0

• 对于events列表中的每个(loc, delta)对（按排序顺序），执行以下操作

  • carrying := carrying + delta

  • 如果carrying > capacity，则

    • 返回False

• 返回True

让我们看看以下实现以获得更好的理解：

示例

 实时演示

class Solution:
   def solve(self, trips, capacity):
      events = []
      for sx, ex, np in trips:
         events.append((sx, np))
         events.append((ex, -np))
      carrying = 0
      for loc, delta in sorted(events):
         carrying += delta
         if carrying > capacity:
            return False
      return True
ob = Solution()
trips = [
   [1, 25, 2],
   [3, 4, 3],
   [5, 12, 3]
]
capacity = 6
print(ob.solve(trips, capacity))

输入

trips = [
[1, 25, 2],
[3, 4, 3],
[5, 12, 3] ]
capacity = 6

输出

True

Arnab Chakraborty

更新于: 2020年10月21日

277 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习