用 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 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

入門