資料結構
網路
關係型資料庫管理系統
作業系統
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 次閱讀
廣告