最小平台数问题
给出了到达和离开时间的列表。现在的问题是要找到铁路所需的最少平台数，因为没有火车在等待。
通过将所有时间按排序顺序进行排序，我们可以轻松找到解决方案，并且可以轻松地跟踪火车何时到达但尚未离开车站。
此问题的时间复杂度为O（nLogn）。
输入输出
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