Pythonでのカープーリング

最初に乗客が利用できる空席のある車両があるとします。車両は東にしか走行しないため、向きを変えて西に走行することはできません。旅行のリスト、trip [i] =[num_passengers、start_location、end_location]を指定しました。これには、i番目の旅行に関する情報が含まれています。つまり、乗車する必要のある乗客の数と、乗車する場所です。そしてそれらを降ろします。ここでは、位置は、車両の最初の位置から真東にあるキロメートル数として示されています。私たちのモジュールは、指定されたすべての旅行ですべての乗客を乗せたり降ろしたりできる場合にのみtrueを返します。したがって、トリップが[[2,1,5]、[3,3,7]]のようで、容量が5の場合、出力はtrueになります。

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

• サイズ1000のstopsという配列を1つ作成し、これを0で埋めます
• 旅行中の私のために
  • ストップ[i[1]]：=ストップ[i [1]] + i [0]
  • ストップ[i[2]]：=ストップ[i [1]] – i [0]
• 停止中のiの場合-
  • 容量：=容量– i
  • 容量が0未満の場合、falseを返します
• 容量>=0の場合はtrueを返します

理解を深めるために、次の実装を見てみましょう-

例

class Solution(object):
   def carPooling(self, trips, capacity):
      stops = [0 for i in range(1001)]
      for i in trips:
         stops[i[1]]+=i[0]
         stops[i[2]]-=i[0]
      for i in stops:
         capacity-=i
         if capacity<0:
            return False
      return capacity>=0
ob = Solution()
print(ob.carPooling([[2,1,5],[3,3,7]],5))

入力

[[2,1,5],[3,3,7]]
5

出力

True