列車の到着・出発時刻から必要な最小プラットフォーム数を求めるアルゴリズム

問題の概要

列車の到着時刻と出発時刻のリストが与えられます。求めるのは、どの列車も駅で待機せずに済むようにするために必要な、プラットフォーム（ホーム）の最小数です。

すべての時刻をあらかじめソートしておけば、この問題は簡単に解けます。「駅に到着したものの、まだ出発していない列車」の数を時系列に沿って追跡することで、同時に駅に存在する列車の最大数、すなわち必要なプラットフォームの最小数が分かります。

このアルゴリズムの計算量は O(n log n) であり、その大部分はソート処理にかかるコストです。

入力と出力

入力：
到着時刻と出発時刻のリスト
Arrival: {900, 940, 950, 1100, 1500, 1800}
Departure: {910, 1200, 1120, 1130, 1900, 2000}

出力：
必要な最小プラットフォーム数: 3

アルゴリズム

入力： 到着時刻のリスト、出発時刻のリスト、およびリストの要素数 n

出力： 問題を解くために必要なプラットフォームの最小数

基本的な考え方は次のとおりです。

• 到着時刻と出発時刻をそれぞれ独立に昇順ソートします。
• 2つのポインタ i（到着側）と j（出発側）を使い、時系列順にイベントを処理します。
• arrival[i] < departure[j] の場合は、既存の列車が出発する前に新しい列車が到着するため、使用中のプラットフォーム数を1増やします。
• それ以外の場合は列車が出発するため、使用中のプラットフォーム数を1減らします。
• 処理中の platform の最大値が答えとなります。

手続き minPlatform(arrival, departure, n)

開始
    到着時刻リストと出発時刻リストをそれぞれソートする
    platform := 1、minPlatform := 1 とする
    i := 1、j := 0 とする

    到着リストのインデックス i と出発リストのインデックス j について繰り返す
        もし arrival[i] < departure[j] ならば
            platform := platform + 1
            i := i + 1
            もし platform > minPlatform ならば
                minPlatform := platform
        そうでなければ
            platform := platform − 1
            j := j + 1
    繰り返し終了
    minPlatform を返す
終了

C++による実装例

以下は、上記のアルゴリズムをC++で実装した例です。

#include<iostream>
#include<algorithm>
using namespace std;

int minPlatform(int arrival[], int departure[], int n) {
    sort(arrival, arrival+n);       // 到着時刻と出発時刻をソート
    sort(departure, departure+n);

    int platform = 1, minPlatform = 1;
    int i = 1, j = 0;

    while (i < n && j < n) {
        if (arrival[i] < departure[j]) {
            platform++;             // 使用中のプラットフォームを1つ増やす
            i++;
            if (platform > minPlatform)   // 最大値を更新
                minPlatform = platform;
        } else {
            platform--;             // 列車が出発し、プラットフォームを1つ解放
            j++;
        }
    }
    return minPlatform;
}

int main() {
    int arrival[] = {900, 940, 950, 1100, 1500, 1800};
    int departure[] = {910, 1200, 1120, 1130, 1900, 2000};
    int n = 6;
    cout << "Minimum Number of Platforms Required: " << minPlatform(arrival, departure, n);
}

出力結果

Minimum Number of Platforms Required: 3

実行例の解説

この例では、時刻をソートすると到着時刻は {900, 940, 950, 1100, 1500, 1800}、出発時刻は {910, 1120, 1130, 1200, 1900, 2000} となります。

午前11時台に注目すると、9:40に到着した列車（12:00出発）、9:50に到着した列車（11:20出発）、11:00に到着した列車（11:30出発）の3本が同時に駅に停まっている瞬間があります。このため、最低でも3つのプラットフォームが必要であることが分かります。

補足：同一時刻の扱い

このアルゴリズムでは比較に「厳密な不等号（<）」を使用しているため、到着時刻と出発時刻が同じ場合には、先に出発する列車がプラットフォームを解放してから次の列車が到着するものとして扱われます。実際の運用条件に応じて、この比較条件は適宜調整することが可能です。