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 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習