最小平台数问题

给出了到达和离开时间的列表。现在的问题是要找到铁路所需的最少平台数，因为没有火车在等待。

通过将所有时间按排序顺序进行排序，我们可以轻松找到解决方案，并且可以轻松地跟踪火车何时到达但尚未离开车站。

此问题的时间复杂度为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