C++ में मीटिंग रूम्स II - न्यूनतम कॉन्फ्रेंस रूम गिनें

समस्या विवरण

मान लीजिए मीटिंग समय अंतराल की एक सरणी है। दो समय प्रारंभ और समाप्ति समय [[s1,e1],[s2,e2],...] हैं और प्रत्येक जोड़ी नियम (si < ei) को संतुष्ट करती है। हमें आवश्यक न्यूनतम कॉन्फ्रेंस रूम की संख्या ढूंढनी है।

उदाहरण के लिए, यदि इनपुट [[0, 30], [5, 10], [15, 20]] है, तो आउटपुट 2 होगा।

समाधान दृष्टिकोण

मिन-हीप (प्रायोरिटी कतार) का उपयोग करके ओवरलैपिंग मीटिंग ट्रैक करें:

1. एक प्रायोरिटी कतार pq परिभाषित करें (समाप्ति समय के आधार पर मिन-हीप)
2. अंतराल सरणी को सॉर्ट करें
3. ret := 0
4. प्रत्येक अंतराल के लिए:
   • जब तक pq खाली नहीं है और pq का शीर्ष तत्व <= वर्तमान अंतराल का प्रारंभ समय:
     • pq से हटाएं (मीटिंग समाप्त हो गई)
   • वर्तमान अंतराल को pq में डालें
   • ret = max(ret, pq का आकार) अपडेट करें
5. ret लौटाएं

C++ कार्यान्वयन

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

struct Comparator{ 
    bool operator()(vector <int>& a, vector <int>& b){ 
        return !(a[1] < b[1]); 
    } 
}; 

class Solution { 
public: 
    static bool cmp(vector <int> a, vector <int> b){ 
        return (a[1] < b[1]); 
    } 
    
    int minMeetingRooms(vector<vector<int>>& intervals) { 
        priority_queue<vector<int>, vector<vector<int>>, Comparator> pq; 
        sort(intervals.begin(), intervals.end()); 
        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}}

आउटपुट

2