최소 플랫폼 수 문제

도착 및 출발 시간 목록이 제공됩니다. 이제 문제는 기차가 기다리지 않기 때문에 철도에 필요한 최소 플랫폼 수를 찾는 것입니다.

모든 타이밍을 정렬된 순서로 정렬하면 솔루션을 쉽게 찾을 수 있습니다. 기차가 도착했지만 역을 떠나지 않았을 때 추적하기가 쉬울 것입니다.

이 문제의 시간 복잡도는 O(n Log n)입니다.

입력 및 출력

Input:
Lists of arrival time and departure time.
Arrival: {900, 940, 950, 1100, 1500, 1800}
Departure: {910, 1200, 1120, 1130, 1900, 2000}
Output:
Minimum Number of Platforms Required: 3

알고리즘

minPlatform(arrival, departure, int n)

입력 - 도착 시간 및 출발 시간 목록 및 목록의 항목 수

출력 - 문제를 해결하려면 최소한의 플랫폼이 필요합니다.

Begin
   sort arrival time list, and departure time list
   platform := 1 and minPlatform := 1
   i := 1 and j := 0

   for elements in arrival list ‘i’ and departure list ‘j’ do
      if arrival[i] < departure[j] then
         platform := platform + 1
         i := i+1
         if platform > minPlatform then
            minPlatform := platform
      else
         platform := platform – 1
         j := j + 1
   done
   return minPlatform
End

예시

#include<iostream>
#include<algorithm>
using namespace std;

int minPlatform(int arrival[], int departure[], int n) {
   sort(arrival, arrival+n);     //sort arrival and departure times
   sort(departure, departure+n);

   int platform = 1, minPlatform = 1;
   int i = 1, j = 0;

   while (i < n && j < n) {
      if (arrival[i] < departure[j]) {
         platform++;     //platform added
         i++;
         if (platform > minPlatform)    //if platform value is greater, update minPlatform
            minPlatform = platform;
      } else {
         platform--;      //delete platform
         j++;
      }
   }
   return minPlatform;
}

int main() {
   int arrival[] = {900, 940, 950, 1100, 1500, 1800};
   int departure[] = {910, 1200, 1120, 1130, 1900, 2000};
   int n = 6;
   cout << "Minimum Number of Platforms Required: " << minPlatform(arrival, departure, n);
}

출력

Minimum Number of Platforms Required: 3