घटनाओं की अधिकतम संख्या जिन्हें C++ में भाग लिया जा सकता है

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=ईवेंट की संख्या, फिर प्रारंभ तिथि के आधार पर ईवेंट सूची को सॉर्ट करें, ret सेट करें:=0 और itr:=0

• pq नामक मैक्स-हीप के आधार पर एक प्राथमिकता कतार बनाएं

• I के लिए 1 से 10000 की सीमा में

  • जबकि itr

    • ईवेंट सम्मिलित करें[itr, 1]

    • आईटीआर को 1 से बढ़ाएं

  • जबकि pq खाली नहीं है और pq के ऊपर . है

    • pq से तत्व हटाएं

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

• वापसी रिट

उदाहरण (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;
   }
};
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