समस्या कथन
एक रेलवे स्टेशन पर पहुंचने वाली सभी ट्रेनों के आगमन और प्रस्थान समय दिए गए हैं, कार्य रेलवे स्टेशन के लिए आवश्यक न्यूनतम प्लेटफॉर्म की संख्या ढूंढना है ताकि कोई ट्रेन प्रतीक्षा न करे।
हमें दो सरणियां दी गई हैं जो उन ट्रेनों के आगमन और प्रस्थान समय का प्रतिनिधित्व करती हैं जो रुकती हैं।
नीचे दिए गए इनपुट के लिए, हमें कम से कम 3 प्लेटफॉर्म की आवश्यकता है:
| Train | Arrival | Departure |
|---|---|---|
| Train-1 | 09:00 | 09:15 |
| Train-2 | 09:35 | 11:45 |
| Train-3 | 09:40 | 11:05 |
| Train-4 | 11:00 | 12:00 |
| Train-5 | 14:30 | 18:15 |
| Train-6 | 18:00 | 19:00 |
एल्गोरिदम
1. आगमन और प्रस्थान समय सरणियों को आरोही क्रम में सॉर्ट करें 2. किसी भी समय ट्रेनों की संख्या को ट्रैक करें, उन ट्रेनों को ध्यान में रखते हुए जो आ चुकी हैं लेकिन प्रस्थान नहीं की हैं
C++ उदाहरण
#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int getPlatformCount(int *arrival, int *departure, int n) {
sort(arrival, arrival + n);
sort(departure, departure + n);
int platformCnt = 1, result = 1;
int i = 1, j = 0;
while (i < n && j < n) {
if (arrival[i] <= departure[j]) {
++platformCnt;
++i;
if (platformCnt > result) result = platformCnt;
} else {
--platformCnt;
++j;
}
}
return result;
}
int main() {
int arrival[] = {900, 935, 940, 1100, 1430, 1800};
int departure[] = {915, 1145, 1105, 1200, 1815, 1900};
cout << "Minimum required platforms = " << getPlatformCount(arrival, departure, SIZE(arrival)) << endl;
return 0;
}
आउटपुट
Minimum required platforms = 3