数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究所需最少站台数问题
现在的问题是，对于给定到达和离开时间，找出铁路所需的最小站台数（所有火车都不能等待）。
通过按顺序对所有时间排序，我们很容易就能找到解决方案，这就便于跟踪火车到达但尚未离开车站的时间。
此问题的以下时间复杂度为 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
更新日期： 15-6-2020
581 次浏览
广告