Pythonでカープーリング問題を解く方法

ある車両があり、最初に乗客用の空席が capacity 分だけ用意されているとします。この車両は東方向にしか走行できないため、折り返して西へ戻ることはできません。ここで、trip[i] = [num_passengers, start_location, end_location] という形式の乗車情報リスト trips が与えられます。num_passengers は乗車させる人数、start_location と end_location はそれぞれ乗客を乗せる地点と降ろす地点です。なお、各地点は車両の初期位置から東方向への距離（キロメートル）として表されます。

このモジュールは、与えられたすべての乗車について全員の乗降が可能である場合にのみ true を返す必要があります。

例えば、trips = [[2,1,5],[3,3,7]]、capacity = 5 の場合、出力は true になります。

解法のアプローチ

この問題は「差分（イベント）方式」を使うと効率的に解けます。手順は以下の通りです。

• サイズ 1001 の配列 stops を作成し、すべての要素を 0 で初期化する
• trips 内の各乗車 i に対して以下を処理する
  • 乗車地点：stops[i[1]] += i[0]（その地点で乗客数が増える）
  • 降車地点：stops[i[2]] -= i[0]（その地点で乗客数が減る）
• stops を先頭から順に走査し、capacity を累積的に更新する
  • capacity -= i を実行し、capacity が負になった時点で false を返す
• 最後まで処理できれば、capacity >= 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

計算量について

このアルゴリズムの時間計算量は O(n + m) です（n は乗車数、m は地点配列のサイズ）。空間計算量は O(m) となります。乗車ごとに区間を個別に比較する方法よりもシンプルで、バグも発生しにくいのが特徴です。