資料結構
網路
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 次瀏覽
廣告