資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中可提供停車的列車最大數量
在這個問題中，我們得到一個數字N，表示一個車站擁有的站臺數量（每個站臺有兩條軌道）。將有T列火車經過該車站，它們的到達和離開時間已知。每列火車停靠在一個特定的車站。我們的任務是建立一個程式，用C++查詢可以提供停車的最大列車數量。
讓我們舉個例子來理解這個問題：
輸入
N = 3, T = 5
Trains = {{0915, 0930, 2}, {0930, 0945, 1}, {0930, 1200, 1}, {0910, 0925, 3}, {0940, 1015, 1}}輸出
4
解釋
The train schedules are, Train 1: Train will be stopped at platform 2 - 09:15-09:30 Train 2: Train will be stopped at platform 1 - 09:30-09:45 Train 3: Train will be not be stopped Train 4: Train will be stopped at platform 3 - 09:10-09:25 Train 5: Train will be stopped at platform 1 - 09:40-10:15
解決方案方法
這個問題的解決方案需要應用貪婪演算法，因為我們需要找到可以在車站停靠的最大火車數量。
我們將使用活動選擇方法來找到問題的最佳解決方案。因此，對於每個站臺，我們將建立一個向量來儲存火車的相關資訊。然後找到最佳解決方案。
示例
演示我們問題的程式：
#include <bits/stdc++.h>
using namespace std;
int maxStop(int trains[][3], int N, int T) {
vector<pair<int, int> > tStopping[N + 1];
int trainsStopped = 0;
for (int i = 0; i < T; i++)
tStopping[trains[i][2]].push_back( make_pair(trains[i][1], trains[i][0]));
for (int i = 0; i <= N; i++)
sort(tStopping[i].begin(), tStopping[i].end());
for (int i = 0; i <= N; i++) {
if (tStopping[i].size() == 0)
continue;
int a = 0;
trainsStopped++;
for (int j = 1; j < tStopping[i].size(); j++) {
if (tStopping[i][j].second >= tStopping[i][a].first) {
a = j;
trainsStopped++;
}
}
}
return trainsStopped;
}
int main(){
int N = 3;
int T = 5;
int trains[T][3] = {{915, 930, 2}, {930, 945, 3}, {930, 1200, 1}, {910, 925, 3}, {940, 1015, 1}};
cout<<"The Maximum No. of Trains Stopped at the station is "<<maxStop(trains, N, T);
return 0;
}輸出
The Maximum No. of Trains Stopped at the station is 4
更新於：2020年10月15日
227 次檢視
廣告