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