C++ 中最多可停列车的数量
c++server side programmingprogramming
在这个问题中，我们给定一个数字 N，表示一个车站拥有的双轨站台数量。T 列列车将经过给定到达和出发时间的车站。每列列车停靠一个特定的车站。我们的任务是编写一个程序，用 C++ 语言找出最多可以停靠的列车数量。
让我们举个例子来理解这个问题:
输入
N = 3, T = 5
列车数量 = {{0915, 0930, 2}, {0930, 0945, 1}, {0930, 1200, 1}, {0910, 0925, 3}, {0940, 1015, 1}}
输出
4
解释
列车时刻表如下: 列车 1:列车将停靠在 2 号站台 - 09:15-09:30 2号列车:列车将在1号站台停靠 - 09:30-09:45 3号列车:列车不会停靠 4号列车:列车将在3号站台停靠 - 09:10-09:25 5号列车:列车将在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
