मान लीजिए कि हमारे पास एक पंक्ति में N बल्ब हैं और उनकी संख्या 1 से N तक है। सबसे पहले, सभी बल्ब बंद हैं। हम प्रतिदिन ठीक एक बल्ब को तब तक चालू कर सकते हैं जब तक कि N दिनों के बाद सभी बल्ब चालू न हो जाएं। यदि हमारे पास लंबाई N का एक सरणी बल्ब है जहां बल्ब [i] =x यह इंगित करता है कि (i+1)वें दिन, हम बल्ब को स्थिति x पर चालू करेंगे। यदि हमारे पास एक और पूर्णांक K है, जैसे कि न्यूनतम दिन संख्या इस तरह से मौजूद है कि दो चालू बल्ब मौजूद हैं जिनके बीच बिल्कुल K बल्ब हैं जो सभी बंद हैं। अगर ऐसा कोई दिन नहीं है, तो -1 लौटें।
इसलिए, यदि इनपुट बल्ब की तरह है:[1,3,2] और के =1, तो आउटपुट 2 के रूप में होगा
-
पहले दिन:बल्ब[0] =1, पहला बल्ब चालू होता है:[1,0,0]
-
दूसरे दिन:बल्ब[1] =3, फिर तीसरा बल्ब चालू होता है:[1,0,1]
-
तीसरे दिन:बल्ब[2] =2, फिर दूसरा बल्ब चालू होता है:[1,1,1]
हम 2 वापस करेंगे क्योंकि दूसरे दिन, दो बल्ब ऑन थे और उनके बीच एक ऑफ बल्ब था।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
n :=बल्बों का आकार
-
इनिशियलाइज़ i:=0 के लिए, जब i
-
दिन [बल्ब[i] - 1] =i + 1
-
-
बाएँ:=0, दाएँ:=k + 1, ret:=inf
-
इनिशियलाइज़ करने के लिए:=0, जब राइट
-
अगर दिन [i] <दिन [बाएं] या दिन [i] <=दिन [दाएं], तो -
-
अगर मैं सही के समान हूं, तो -
-
रिट :=न्यूनतम सेवानिवृत्त और अधिकतम दिन[बाएं] और दिन[दाएं]
-
-
बायां :=मैं
-
दाएँ :=i + k + 1
-
-
-
वापसी (यदि रिट inf के समान है, तो -1, अन्यथा रिट)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int kEmptySlots(vector<int>& bulbs, int k) {
int n = bulbs.size();
vector<int> days(n);
for (int i = 0; i < n; i++) {
days[bulbs[i] - 1] = i + 1;
}
int left = 0;
int right = k + 1;
int ret = INT_MAX;
for (int i = 0; right < n; i++) {
if (days[i] < days[left] || days[i] <= days[right]) {
if (i == right) {
ret = min(ret, max(days[left], days[right]));
}
left = i;
right = i + k + 1;
}
}
return ret == INT_MAX ? -1 : ret;
}
};
main(){
Solution ob;
vector<int> v = {1,3,2};
cout << (ob.kEmptySlots(v, 1));
} इनपुट
{1,3,2}, आउटपुट
2
