Trong bài toán này, chúng ta được đưa ra một số N biểu thị số lượng sân ga mà một nhà ga có hai đường ray. Và các chuyến tàu T sẽ đi qua ga có thời gian đến và đi được cho trước. Mỗi chuyến tàu dừng ở một ga cụ thể. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm các chuyến tàu Tối đa mà điểm dừng có thể được cung cấp trong C ++.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
N = 3, T = 5
Trains = {{0915, 0930, 2}, {0930, 0945, 1}, {0930, 1200, 1}, {0910, 0925, 3}, {0940, 1015, 1}} Đầu ra
4
Giải thích
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
Phương pháp tiếp cận giải pháp
Giải pháp cho vấn đề này cần áp dụng một cách tiếp cận tham lam vì chúng ta cần tìm số lượng tàu tối đa có thể dừng tại ga.
Chúng tôi sẽ sử dụng phương pháp lựa chọn hoạt động để tìm ra giải pháp tối ưu nhất cho vấn đề. Vì vậy, đối với mỗi nền tảng, chúng tôi sẽ tạo một vectơ để lưu trữ thông tin của chuyến tàu. Và sau đó tìm ra giải pháp tối ưu nhất.
Ví dụ
Chương trình minh họa cách giải quyết vấn đề của chúng tôi,
#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;
} Đầu ra
The Maximum No. of Trains Stopped at the station is 4