C++ . में K खाली स्लॉट

मान लीजिए कि हमारे पास एक पंक्ति में 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