C++ में अटेंड किए जा सकने वाले इवेंट्स की अधिकतम संख्या

मान लीजिए हमारे पास इवेंट्स का एक ऐरे है जहां events[i] = [startDayi, endDayi]। यहां हर इवेंट i startDayi पर शुरू होता है और endDayi पर खत्म होता है। हम किसी इवेंट i को किसी भी दिन d पर अटेंड कर सकते हैं जहां d startTimei और endTimei की रेंज में है (दोनों इन्क्लूसिव)। हमें ध्यान रखना होगा कि हम किसी भी समय केवल एक इवेंट अटेंड कर सकते हैं। तो हम अटेंड कर सकने वाले इवेंट्स की अधिकतम संख्या ढूंढें। उदाहरण के लिए, अगर इनपुट [[1,4], [4,4], [2,2], [3,4], [1,1]] है, तो आउटपुट 4 होगा, क्योंकि हम अधिकतम चार इवेंट्स अटेंड कर सकते हैं, ये हैं [1, 1], [2, 2], [3, 4] और [4, 4]।

इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:

• n := इवेंट्स की संख्या, फिर इवेंट लिस्ट को स्टार्ट डेट के आधार पर सॉर्ट करें, ret := 0 और itr := 0 सेट करें

• मिन-हीप बेस्ड प्रायोरिटी क्यू pq बनाएं

• i को 1 से 100000 तक लूप करें:

  • जब तक itr < n और events[itr][0] = i:

    • events[itr][1] इंसर्ट करें

    • itr को 1 से बढ़ाएं

  • जब तक pq खाली नहीं है और pq का टॉप < i:

    • pq से एलिमेंट डिलीट करें

  • अगर pq खाली नहीं है, तो pq से डिलीट करें और ret को 1 से बढ़ाएं

• ret लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्न इम्प्लीमेंटेशन देखें:

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

class Solution {
public:
    static bool cmp(vector <int>& a, vector <int>& b){
        return a[0] < b[0];
    }
    int maxEvents(vector<vector<int>>& events) {
        int n = events.size();
        sort(events.begin(), events.end(), cmp);
        int ret = 0;
        int itr = 0;
        priority_queue <int, vector <int>, greater <int>> pq;
        for(int i = 1; i <= 1e5; i++){
            while(itr < n && events[itr][0] == i){
                pq.push(events[itr][1]);
                itr++;
            }
            while(!pq.empty() && pq.top() < i) pq.pop();
            if(!pq.empty()){
                pq.pop();
                ret++;
            }
        }
        return ret;
    }
};

int main(){
    vector<vector<int>> v = {{1,4},{4,4},{2,2},{3,4},{1,1}};
    Solution ob;
    cout << (ob.maxEvents(v));
}

इनपुट

[[1,4],[4,4],[2,2],[3,4],[1,1]]

आउटपुट

4