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

मान लीजिए हमारे पास एक पंक्ति में N बल्ब हैं और वे 1 से N तक नंबर दिए गए हैं। पहले, सभी बल्ब बंद हैं। हम हर दिन ठीक एक बल्ब चालू कर सकते हैं जब तक कि N दिनों के बाद सभी बल्ब चालू न हो जाएं। यदि हमारे पास bulbs नामक लंबाई N का एक ऐरे है जहां bulbs[i] = x इसका संकेत देता है कि (i+1)वें दिन, हम स्थिति x पर बल्ब चालू करेंगे। यदि हमारे पास एक और पूर्णांक K है, जैसे कि न्यूनतम दिन संख्या ढूंढनी है जहां दो चालू बल्ब मौजूद हों जिनके बीच ठीक K बल्ब हों जो सभी बंद हों। यदि ऐसा कोई दिन नहीं है, तो -1 लौटाएं।

तो, यदि इनपुट bulbs: [1,3,2] और K = 1 है, तो आउटपुट 2 होगा क्योंकि:

• पहले दिन: bulbs[0] = 1, पहला बल्ब चालू: [1,0,0]

• दूसरे दिन: bulbs[1] = 3, फिर तीसरा बल्ब चालू: [1,0,1]

• तीसरे दिन: bulbs[2] = 2, फिर दूसरा बल्ब चालू: [1,1,1]

हम 2 लौटाएंगे क्योंकि दूसरे दिन, दो चालू बल्ब थे जिनके बीच एक बंद बल्ब था।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• n := bulbs का आकार

• i := 0 से शुरू करें, जब i < n, अपडेट करें (i को 1 से बढ़ाएं), करें:

  • days[bulbs[i] - 1] = i + 1

• लेफ्ट := 0, राइट := k + 1, रेट := इन्फ

• i := 0 से शुरू करें, जब राइट < n, अपडेट करें (i को 1 से बढ़ाएं), करें:

  • यदि days[i] < days[लेफ्ट] या days[i] <= days[राइट], तो:

    • यदि i, राइट के समान है, तो:

      • रेट := रेट और max(days[लेफ्ट], days[राइट]) का न्यूनतम

    • लेफ्ट := i

    • राइट := i + k + 1

• लौटाएं (यदि रेट, इन्फ के समान है, तो -1, अन्यथा रेट)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int kEmptySlots(vector& bulbs, int k) {
        int n = bulbs.size();
        vector 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;
    }
};

int main() {
    Solution ob;
    vector v = {1,3,2};
    cout << (ob.kEmptySlots(v, 1));
}

इनपुट

{1,3,2}, 1

आउटपुट

2