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 に 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

計算量について

トリップの数を N とすると、イベントは 2N 個生成され、ソートに O(N log N)、その後の走査に O(N) かかるため、全体の時間計算量は O(N log N) です。単純に各区間ごとに乗客数を数える O(N²) の方法よりも大幅に高速で、大量のリクエストにも対応できます。