प्लेटफ़ॉर्म समस्या की न्यूनतम संख्या

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

सभी समयों को क्रमबद्ध क्रम में क्रमबद्ध करके, हम आसानी से समाधान ढूंढ सकते हैं, ट्रेन के आने पर ट्रैक करना आसान होगा लेकिन स्टेशन से नहीं छोड़ा।

इस समस्या की समय जटिलता O(n Log n) है।

इनपुट और आउटपुट

Input:
Lists of arrival time and departure time.
Arrival: {900, 940, 950, 1100, 1500, 1800}
Departure: {910, 1200, 1120, 1130, 1900, 2000}
Output:
Minimum Number of Platforms Required: 3

एल्गोरिदम

minPlatform(arrival, departure, int n)

इनपुट - आगमन समय और प्रस्थान समय की सूची, और सूची में मदों की संख्या

आउटपुट - समस्या को हल करने के लिए न्यूनतम प्लेटफ़ॉर्म की संख्या आवश्यक है।

Begin
   sort arrival time list, and departure time list
   platform := 1 and minPlatform := 1
   i := 1 and j := 0

   for elements in arrival list ‘i’ and departure list ‘j’ do
      if arrival[i] < departure[j] then
         platform := platform + 1
         i := i+1
         if platform > minPlatform then
            minPlatform := platform
      else
         platform := platform – 1
         j := j + 1
   done
   return minPlatform
End

उदाहरण

#include<iostream>
#include<algorithm>
using namespace std;

int minPlatform(int arrival[], int departure[], int n) {
   sort(arrival, arrival+n);     //sort arrival and departure times
   sort(departure, departure+n);

   int platform = 1, minPlatform = 1;
   int i = 1, j = 0;

   while (i < n && j < n) {
      if (arrival[i] < departure[j]) {
         platform++;     //platform added
         i++;
         if (platform > minPlatform)    //if platform value is greater, update minPlatform
            minPlatform = platform;
      } else {
         platform--;      //delete platform
         j++;
      }
   }
   return minPlatform;
}

int main() {
   int arrival[] = {900, 940, 950, 1100, 1500, 1800};
   int departure[] = {910, 1200, 1120, 1130, 1900, 2000};
   int n = 6;
   cout << "Minimum Number of Platforms Required: " << minPlatform(arrival, departure, n);
}

आउटपुट

Minimum Number of Platforms Required: 3