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

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

সকল টাইমিংকে সর্ট করা হলে সমাধান সহজে পাওয়া যায়, এটি ট্র্যাক রাখতে সাহায্য করে যে কোন ট্রেন এসে 갔 কিন্তু স্টেশন ছেড়ে যায়নি।

এই সমস্যার টাইম কমপ্লেক্সিটি O(n log n)।

ইনপুট এবং আউটপুট

ইনপুট: আয়валь টাইম এবং ডিপারচার টাইমের তালিকা। Arrival: {900, 940, 950, 1100, 1500, 1800} Departure: {910, 1200, 1120, 1130, 1900, 2000} আউটপুট: Minimum Number of Platforms Required: 3

অ্যালগরিদম

minPlatform(arrival, departure, int n)

ইনপুট - আয়벌 টাইমের তালিকা, ডিপারচার টাইমের তালিকা এবং লিস্টের আইটেম সংখ্যা

আউটপুট - সমস্যা সমাধানের জন্য দরকার ন্যূনতম প্ল্যাটফর্মের সংখ্যা।

শুরু
  আয়벌 টাইম লিস্ট এবং ডিপারচার টাইম লিস্ট সর্ট করুন
  platform := 1 এবং minPlatform := 1
  i := 1 এবং j := 0
  আয়벌 লিস্ট 'i' এবং ডিপারচার লিস্ট 'j'-এর এলিমেন্টের জন্য করুন
    যদি arrival[i] < departure[j] হয়, তবে
      platform := platform + 1
      i := i+1
      যদি platform > minPlatform হয়, তবে
        minPlatform := platform
    অন্যথায়
      platform := platform - 1
      j := j + 1
  শেষ
  minPlatform রিটার্ন করুন
শেষ

উদাহরণ

#include<iostream> #include<algorithm> using namespace std; int minPlatform(int arrival[], int departure[], int n) { sort(arrival, arrival+n); //আয়벌 এবং ডিপারচার টাইম সর্ট করুন 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++; //প্ল্যাটফর্ম যোগ করা হলো i++; if (platform > minPlatform) //যদি platform মান বড় হয়, minPlatform আপডেট করুন minPlatform = platform; } else { 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