C++を使用する鉄道駅に必要なプラットフォームの最小数。

問題の説明

鉄道駅に到着するすべての列車の到着時刻と出発時刻を考えると、列車が待たないように、鉄道駅に必要なプラットフォームの最小数を見つけることがタスクです。

停車する列車の到着時刻と出発時刻を表す2つの配列が与えられます。

以下の入力には、少なくとも3つのプラットフォームが必要です-

アルゴリズム

1. Sort arrival and departure time arrays in ascending order
2. Trace the number of trains at any time keeping track of trains that haves arrived, but not departed

例

#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;
}

出力

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

Minimum required platforms = 3