在这个问题中,我们得到一个数字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