C++ এ অংশগ্রহণ করা যেতে পারে এমন ইভেন্টের সর্বাধিক সংখ্যা

ধরুন আমাদের কাছে ইভেন্টের একটি অ্যারে আছে যেখানে ইভেন্ট[i] =[startDayi, endDayi]। এখানে প্রতিটি ইভেন্ট আমি startDayi এ শুরু করি এবং endDayi এ শেষ করি। আমরা যেকোনো দিন d একটি ইভেন্ট I-এ যোগ দিতে পারি যেখানে d রেঞ্জ startTimei এবং endTimei (উভয়ই অন্তর্ভুক্ত)। আমাদের মনে রাখতে হবে যে আমরা যে কোনো সময় শুধুমাত্র একটি অনুষ্ঠানে যোগ দিতে পারি। তাই আমরা অংশগ্রহণ করতে পারি ইভেন্ট সর্বোচ্চ সংখ্যা খুঁজুন. সুতরাং উদাহরণস্বরূপ, যদি ইনপুটটি [[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

  নামক ম্যাক্স-হিপের উপর ভিত্তি করে একটি অগ্রাধিকার সারি তৈরি করুন

• আমি 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