मान लीजिए हमारे पास n बल्ब्स वाला एक कमरा है, ये 1 से n तक नंबरेड हैं, बाएं से दाएं एक पंक्ति में व्यवस्थित। प्रारंभ में, सभी बल्ब्स बंद हैं। मोमेंट k पर (k के लिए 0 से n-1 की रेंज में), हम light[k] बल्ब को ऑन करते हैं। एक बल्ब केवल तभी नीला होता है जब वह ऑन हो और उसके सभी पिछले बल्ब (बाएं तरफ) भी ऑन हों। हमें उन मोमेंट्स की संख्या ढूंढनी है जिनमें सभी ऑन बल्ब्स नीले हैं। यह एक उदाहरण है:
आउटपुट 3 होगा क्योंकि मोमेंट्स 1, 2 और 4 हैं।
इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:
ret := 0, एक सेट x डिफाइन करें, n := लाइट ऐरे का साइज, एक मैप 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;
}
};
int main(){
vector<int> v = {2,1,3,5,4};
Solution ob;
cout << (ob.numTimesAllBlue(v));
}
इनपुट
[2,1,3,5,4]
आउटपुट
3
