C++で解く！鉄道駅に必要なプラットフォームの最小数を求めるアルゴリズム

問題の概要

ある鉄道駅に到着するすべての列車の到着時刻と出発時刻が与えられたとき、どの列車も待ち時間なく停車できるようにするために必要なプラットフォーム（ホーム）の最小数を求めるのがこの問題です。

入力としては、列車の到着時刻を格納した配列と、出発時刻を格納した配列の2つが与えられます。

例えば以下の入力の場合、最低でも3つのプラットフォームが必要になります。

アルゴリズム

この問題は、時刻を並べ替えて同時進行する列車数を数えるというシンプルな発想で効率的に解くことができます。手順は以下の通りです。

1. 到着時刻の配列と出発時刻の配列をそれぞれ昇順にソートする
2. 「到着済みだがまだ出発していない列車」の数を常に把握しながら、
   各時点で同時に滞在している列車の最大数を追跡する

考え方のポイント

到着時刻と出発時刻を時系列順に比較していき、列車が到着すれば必要なプラットフォーム数を1増やし、列車が出発すれば1減らします。この処理をすべての時刻に対して行い、途中で現れた最大値が答えとなります。

なお、同じ時刻に到着と出発が重なる場合（上のコードでは <= で判定）、到着を先にカウントすることで、実際の運用において安全側の見積もりになります。

C++による実装例

#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int getPlatformCount(int *arrival, int *departure, int n){
    sort(arrival, arrival + n);
    sort(departure, departure + n);
    int platformCnt = 1;
    int result = 1;
    int i = 1;
    int j = 0;
    while (i < n && j < n) {
        if (arrival[i] <= departure[j]) {
            ++platformCnt;
            ++i;
            if (platformCnt > result) {
                result = platformCnt;
            }
        } else {
            --platformCnt;
            ++j;
        }
    }
    return result;
}
int main()
{
    int arrival[] = {900, 935, 940, 1100, 1430, 1800};
    int departure[] = {915, 1145, 1105, 1200, 1815, 1900};
    cout << "Minimum required platforms = " <<
    getPlatformCount(arrival, departure, SIZE(arrival)) << endl;
    return 0;
}

コードの解説

時刻は 900 のような HHMM 形式の整数で表現しており、単純な整数比較だけで大小関係を判定できるのがポイントです。

• i：次に処理する到着時刻のインデックス
• j：次に処理する出発時刻のインデックス
• platformCnt：現在時点で必要なプラットフォーム数
• result：これまでの最大値（＝最終的な答え）

計算量は、ソートに O(n log n)、その後の走査に O(n) かかるため、全体で O(n log n) となります。

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Minimum required platforms = 3