প্ল্যাটফর্ম সমস্যা ন্যূনতম সংখ্যা

আগমন এবং প্রস্থানের সময়ের একটি তালিকা দেওয়া হয়েছে৷ এখন সমস্যা হল রেলওয়ের জন্য ন্যূনতম সংখ্যক প্ল্যাটফর্ম খুঁজে বের করা কারণ কোনো ট্রেন অপেক্ষা করে না।

সমস্ত সময়কে সাজানো ক্রমে সাজানোর মাধ্যমে, আমরা সহজেই সমাধানটি খুঁজে পেতে পারি, ট্রেনটি কখন আসবে কিন্তু স্টেশন থেকে বের হবে না তখন ট্র্যাক করা সহজ হবে৷

এই সমস্যার সময় জটিলতা হল 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