इस समस्या में, हमें एक नंबर 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