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