Pythonで指定されたリストのすべての乗客をピックアップおよびドロップできるかどうかを確認するプログラム

[start_x、end_x、num_passengers]を含む各行にrequested_tripsという行列があり、容量値もあるとします。これで、要求された各旅行では、start_xでnum_passengersの乗客を迎えに行き、end_xで降ろすように求められます。また、指定された容量の車があり、位置x =0から開始します。すべての乗客を乗せたいので、右側にしか移動できません。全員を乗降できるかどうかを確認する必要があります。

したがって、入力がトリップ=[[1、25、2]、[3、4、3]、[5、12、3]]容量=6のような場合、出力はTrueになります

これを解決するには、次の手順に従います-

• イベント：=新しいリスト

• 旅行の各セット（sx、ex、np）について、実行します

  • イベントの最後にペア（sx、np）を挿入します

  • イベントの最後にペア（例、-np）を挿入します

• キャリング：=0

• イベントのリスト（ソートされた順序）の各ペア（loc、delta）について、実行します

  • キャリング：=キャリング+デルタ

  • >容量を運ぶ場合は、

    • 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