न्यूनतम प्लेटफॉर्म समस्या

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

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

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

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

इनपुट: आगमन समय और प्रस्थान समय की सूचियां। आगमन: {900, 940, 950, 1100, 1500, 1800} प्रस्थान: {910, 1200, 1120, 1130, 1900, 2000} आउटपुट: आवश्यक न्यूनतम प्लेटफॉर्म की संख्या: 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