이 문제에서 우리는 스테이션이 각각 2개의 트랙을 가진 플랫폼의 수를 나타내는 숫자 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