C++ का उपयोग करने वाले रेलवे स्टेशन के लिए आवश्यक प्लेटफॉर्मों की न्यूनतम संख्या।

समस्या कथन

रेलवे स्टेशन पर पहुंचने वाली सभी ट्रेनों के आगमन और प्रस्थान के समय को देखते हुए, रेलवे स्टेशन के लिए आवश्यक न्यूनतम प्लेटफॉर्म खोजने का कार्य है ताकि कोई ट्रेन प्रतीक्षा न करे।

हमें दो सरणियाँ दी गई हैं जो रुकने वाली ट्रेनों के आगमन और प्रस्थान समय का प्रतिनिधित्व करती हैं।

नीचे दिए गए इनपुट के लिए, हमें कम से कम 3 प्लेटफॉर्म चाहिए -

एल्गोरिदम

1. Sort arrival and departure time arrays in ascending order
2. Trace the number of trains at any time keeping track of trains that haves arrived, but not departed

उदाहरण

#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;
   int result = 1;
   int i = 1;
   int 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