C++-এ Meeting Rooms II: মিটিং শিডিউলিংয়ে কমপক্ষে কতটি কনফারেন্স রুম লাগবে

মিটিং টাইম ইন্টারভালের একটি অ্যারে দেওয়া আছে (প্রতিটি: [start, end], যেখানে start < end)। একই সময়ে ওভারল্যাপ করার মিটিংগুলো আলাদা রুমে হবে। কমপক্ষে কতটি কনফারেন্স রুম লাগবে তা বের করতে হবে।

উদাহরণ

ইনপুট: [[0, 30], [5, 10], [15, 20]]

আউটপুট: 2

ব্যাখ্যা: [0,30] এবং [5,10] ওভারল্যাপ করে, আবার [0,30] এবং [15,20] ওভারল্যাপ করে। তবে [5,10] এবং [15,20] ওভারল্যাপ করে না। তাই কমপক্ষে ২টি রুম লাগবে।

সমাধানের পদ্ধতি (Min-Heap / Priority Queue)

ইন্টারভালগুলো শুরুর সময় অনুযায়ী সর্ট করুন।
একটি মিন-হিপ (প্রায়োরিটি কিউ) pq ব্যবহার করুন যা মিটিংর এন্ড টাইম ট্র্যাক করবে (সর্বনিম্ন এন্ড টাইম টপে থাকবে)।
ret = 0।
প্রতিটি ইন্টারভাল intervals[i] এর জন্য:
- যখন pq খালি নয় এবং pq.top().end <= intervals[i].start (সর্বোচ্চ পূরন মিটিং শেষ হয়েছে), তবে সেটি পপ করুন (রুম ফ্রি হয়েছে)।
- বর্তমান ইন্টারভাল pq-তে পুশ করুন (নতুন রুম অ্যালোকেট বা পুরনো রিইউজ)।
- ret = max(ret, pq.size()) আপডেট করুন (সর্বোচ্চ সমকാലীন মিটিং = রুম সংখ্যা)।
ret রিটার্ন করুন।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

struct Comparator {
    bool operator()(vector<int>& a, vector<int>& b) {
        return !(a[1] < b[1]); // min-heap based on end time
    }
};

class Solution {
public:
    static bool cmp(vector<int> a, vector<int> b) {
        return (a[0] < b[0]); // sort by start time
    }
    
    int minMeetingRooms(vector<vector<int>>& intervals) {
        priority_queue<vector<int>, vector<vector<int>>, Comparator> pq;
        sort(intervals.begin(), intervals.end(), cmp);
        int ret = 0;
        for (int i = 0; i < intervals.size(); i++) {
            while (!pq.empty() && pq.top()[1] <= intervals[i][0])
                pq.pop();
            pq.push(intervals[i]);
            ret = max(ret, (int)pq.size());
        }
        return ret;
    }
};

int main() {
    vector<vector<int>> v = {{0, 30}, {5, 10}, {15, 20}};
    Solution ob;
    cout << (ob.minMeetingRooms(v));
    return 0;
}

ইনপুট

{{0, 30}, {5, 10}, {15, 20}}