使用C ++的火车站所需的最少平台数量。

问题陈述

给定到达火车站的所有火车的到达和离开时间，任务是找到火车站所需的最少平台数目，以便没有火车在等待。

我们得到了两个数组，分别表示停靠的火车的到达和离开时间。

对于以下输入，我们至少需要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