数据结构
网络
关系型数据库管理系统
操作系统
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
更新于: 2020 年 6 月 15 日
581 次阅读
广告