用 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

Narendra Kumar

已更新于: 31-10-2019

255 次浏览

开启你的职业生涯

通过完成课程获得认证

入门