ধরুন একটি ঘরে nটি বল্ব আছে, এগুলো ১ থেকে n পর্যন্ত নম্বর করা এবং বাম থেকে ডানে সারিয়ে রেখে। শুরুতে সব বল্ব বন্ধ। মুহূর্ত k-এ (k = 0 থেকে n - 1 পর্যন্ত), light[k] বল্ব অন করা হয়। একটি বল্ব ব্লু কালারে পরিণত হয় শুধু তখনই যখন সেটি অন থাকে এবং এর সকল পূর্ববর্তী বল্ব (বামপাশের)ও অন থাকে। আমাদের বের করতে হবে কত মুহূর্তে সব অন করা বল্ব ব্লু হয়। উদাহরণ −
আউটপুট হবে ৩ কারণ মুহূর্তগুলো ১, ২ এবং ৪।
সমাধানের ধাপগুলো:
ret := 0, একটি সেট x ডিফাইন করুন, n := light array-এর সাইজ, একটি map m ডিফাইন করুন
একটি ম্যাক্স হিপ-বেসড প্রায়োরিটি কিউ pq ডিফাইন করুন
i = 0 থেকে n – 1 পর্যন্ত লুপ চালান
m[light[i]] := i এবং i pq-তে পশ করুন
i = 1 থেকে n পর্যন্ত লুপ চালান
m[i] x-এ ইনসার্ট করুন
যখন pq খালি নয় এবং pq-এর টপ এলিমেন্ট x-এ থাকে
pq থেকে পপ করুন
ret := ret + 1 যখন (pq খালি অথবা pq-এর টপ >= i), অন্যথায় 0
res রিটার্ন করুন
উদাহরণ (C++)
নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে −
#include <bits/stdc++.h> using namespace std; class Solution { public: int numTimesAllBlue(vector<int>& light) { int ret = 0; set <int> x; int n = light.size(); map <int, int> m; priority_queue <int, vector <int>, greater <int> > pq; for(int i = 0; i < n; i++){ m[light[i]] = i; pq.push(i); } for(int i = 1; i <=n; i++){ x.insert(m[i]); while(!pq.empty() && x.count(pq.top()))pq.pop(); ret += (pq.empty() || (pq.top() >= i)); } return ret; } }; main(){ vector<int> v = {2,1,3,5,4}; Solution ob; cout << (ob.numTimesAllBlue(v)); }
ইনপুট
[2,1,3,5,4]
আউটপুট
3
