ধরুন আমাদের একটি সারিতে N বাল্ব রয়েছে এবং সেগুলি 1 থেকে N পর্যন্ত সংখ্যা করা হয়েছে। প্রথমে, সমস্ত বাল্ব বন্ধ। N দিনের পরে সমস্ত বাল্ব চালু না হওয়া পর্যন্ত আমরা প্রতিদিন ঠিক একটি বাল্ব চালু করতে পারি। আমাদের যদি N দৈর্ঘ্যের একটি অ্যারে বাল্ব থাকে যেখানে বাল্ব[i] =x এটি নির্দেশ করে যে (i+1)তম দিনে, আমরা x অবস্থানে বাল্বটি চালু করব। যদি আমাদের আরেকটি পূর্ণসংখ্যা K থাকে, যেমন ন্যূনতম দিনের সংখ্যা যেমন দুটি চালু বাল্ব আছে যেগুলির মধ্যে ঠিক K বাল্ব আছে যেগুলি সব বন্ধ। যদি এমন কোন দিন না থাকে, তাহলে ফিরুন -1।
সুতরাং, যদি ইনপুটটি বাল্বের মত হয়:[1,3,2] এবং K =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
-
আরম্ভ করার জন্য i :=0, যখন ডান
-
যদি দিন[i] <দিন[বাম] বা দিন[i] <=দিন[ডান], তাহলে -
-
যদি আমি সঠিক হিসাবে একই হয়, তাহলে -
-
ret :=সর্বনিম্ন ret এবং সর্বাধিক দিন [বাম] এবং দিন [ডান]
-
-
বাম :=i
-
ডান:=i + k + 1
-
-
-
রিটার্ন (যদি ret একই হয় inf, তাহলে -1, অন্যথায় ret)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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
