C++で停車可能な最大列車数を求める方法

問題概要

この問題では、駅にあるプラットホームの数 N(各プラットホームは2本の線路を持つ)と、到着時刻・出発時刻付きの T 本の列車の情報が与えられます。各列車は特定のプラットホームに停車します。私たちの課題は、C++を用いて、停車扱いが可能な列車の最大数を求めるプログラムを作成することです。

具体例を使って問題を確認しましょう。

入力

N = 3, T = 5
Trains = {{0915, 0930, 2}, {0930, 0945, 1}, {0930, 1200, 1}, {0910, 0925, 3}, {0940, 1015, 1}}

出力

4

説明

列車の運行スケジュールは以下の通りです。
列車1: プラットホーム2に停車(09:15〜09:30)
列車2: プラットホーム1に停車(09:30〜09:45)
列車3: 停車不可
列車4: プラットホーム3に停車(09:10〜09:25)
列車5: プラットホーム1に停車(09:40〜10:15)

なお、各列車のデータは「到着時刻」「出発時刻」「担当プラットホーム番号」の3つの値の組で表現されています。

解法アプローチ

この問題の解法には貪欲法(グリーディーアプローチ)を採用します。「駅に停車できる列車の数を最大化する」という目的に対して、局所的に最良の選択を繰り返すことで全体の最適解が得られる構造になっているからです。

最適な解を導くため、古典的な活動選択問題(Activity Selection Problem)の考え方を応用します。具体的な手順は以下の通りです。

• 各プラットホームごとに vector を作成し、そのホームに割り当てられた列車の情報(出発時刻・到着時刻のペア)を格納します。
• 各プラットホーム内の列車を、出発時刻の早い順にソートします。
• 各ホームでは最初の列車を必ず選択し、その後は「直前に選んだ列車の出発時刻以降に到着する列車」だけを順番に選んでいきます。

出発(終了)時刻の早い列車から優先的に選ぶことで、1本の線路で受け入れられる列車数が最大化され、結果として駅全体での最大停車列車数が求まります。

C++実装例

以下は、このアルゴリズムの動作を示すサンプルプログラムです。

#include <bits/stdc++.h>
using namespace std;
int maxStop(int trains[][3], int N, int T) {
    vector<pair<int, int> > tStopping[N + 1];
    int trainsStopped = 0;
    for (int i = 0; i < T; i++)
        tStopping[trains[i][2]].push_back(make_pair(trains[i][1], trains[i][0]));
    for (int i = 0; i <= N; i++)
        sort(tStopping[i].begin(), tStopping[i].end());
    for (int i = 0; i <= N; i++) {
        if (tStopping[i].size() == 0)
            continue;
        int a = 0;
        trainsStopped++;
        for (int j = 1; j < tStopping[i].size(); j++) {
            if (tStopping[i][j].second >= tStopping[i][a].first) {
                a = j;
                trainsStopped++;
            }
        }
    }
    return trainsStopped;
}
int main(){
    int N = 3;
    int T = 5;
    int trains[T][3] = {{915, 930, 2}, {930, 945, 3}, {930, 1200, 1}, {910, 925, 3}, {940, 1015, 1}};
    cout<<"The Maximum No. of Trains Stopped at the station is "<<maxStop(trains, N, T);
    return 0;
}

出力

The Maximum No. of Trains Stopped at the station is 4

計算量

• 時間計算量: O(T log T) ― 全列車をプラットホーム別に振り分けた後、各グループをソートする必要があるためです。
• 空間計算量: O(T) ― 列車の情報を格納するためのベクターが必要になります。

まとめ

「停車可能な最大列車数」の問題は、各プラットホームを独立した資源とみなし、活動選択問題の貪欲戦略を適用することで効率的に解くことができます。出発時刻の早い列車から順に選んでいくことで、限られた線路リソースを最大限に活用し、最適な停車スケジュールを実現できます。