C++ ব্যবহার করে রেলওয়ে স্টেশনের জন্য ন্যূনতম প্ল্যাটফর্ম সংখ্যা বের করা

সমস্যা বিবরণ

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

আমাদের দুটি অ্যারে দেওয়া আছে যা ট্রেনগুলোর আগমন ও প্রস্থান সময় উপস্থাপন করে।

নিচের ইনপুটের জন্য কমপক্ষে ৩টি প্ল্যাটফর্ম দরকার:

এলগরিদম

1. আগমন ও প্রস্থান সময়ের অ্যারে দুটিকে আরোহী ক্রমে সর্ট করুন
2. যেকোনো সময়ে কতগুলো ট্রেন উপস্থিত আছে তা ট্র্যাক করুন, 벌써 পৌঁছানো কিন্তু এখনো যাওয়া নিয়ে যাওয়া ট্রেনগুলো গণনা করে

উদাহরণ কোড

#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