C++で停止できる最大列車

この問題では、ステーションがそれぞれ2つのトラックを持つプラットフォームの数を示す数値Nが与えられます。そして、T列車は到着時刻と出発時刻が指定されている駅を通過します。各列車は特定の駅に停車します。私たちのタスクは、C++で停止を提供できる最大列車を見つけるプログラムを作成することです。

問題を理解するために例を見てみましょう

入力

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

出力

4

説明

The train schedules are,
Train 1: Train will be stopped at platform 2 - 09:15-09:30
Train 2: Train will be stopped at platform 1 - 09:30-09:45
Train 3: Train will be not be stopped
Train 4: Train will be stopped at platform 3 - 09:10-09:25
Train 5: Train will be stopped at platform 1 - 09:40-10:15

ソリューションアプローチ

駅に停車できる列車の最大数を見つける必要があるため、この問題の解決策には貪欲なアプローチを適用する必要があります。

アクティビティ選択アプローチを使用して、問題の最適な解決策を見つけます。そのため、プラットフォームごとに、列車の情報を格納するためのベクトルを作成します。そして、最適なソリューションを見つけます。

例

私たちの問題の働きを説明するプログラム

#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