ধরুন events[i] = [startDayi, endDayi] এমন একটি ইভেন্ট অ্যারে আছে। প্রতিটি ইভেন্ট i startDayi-তে শুরু হয় এবং endDayi-তে শেষ হয়। আমরা ইভেন্ট i যেকোনো দিন d-এ অনুষ্ঠান করতে পারি যেখানে d startDayi এবং endDayi-এর মধ্যে (দুটোই ইনক্লুসিভ)। একসাথে একাধিক ইভেন্ট অনুষ্ঠান করা যাবে না। সর্বোচ্চ কতগুলো ইভেন্ট অনুষ্ঠান করা যায় তা বের করতে হবে। ইনপুট [[1,4], [4,4], [2,2], [3,4], [1,1]] হলে আউটপুট ৪, কারণ অনুষ্ঠান করা যায় [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] pq-তে পশ করুন
itr ১ বাড়ান
যখন pq খালি নয় এবং pq-এর টপ < i
pq থেকে পপ করুন
যদি pq খালি নয়, তবে pq থেকে পপ করুন এবং ret ১ বাড়ান
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; } }; 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
