इस समस्या में, हमें एक संख्या 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<<"स्टेशन पर रोकी गई ट्रेनों की अधिकतम संख्या है "<<maxStop(trains, N, T); return 0; }
आउटपुट
स्टेशन पर रोकी गई ट्रेनों की अधिकतम संख्या है 4
