ধরুন আমাদের কাছে অন্তর্বর্তীগুলির একটি তালিকা আছে, যেখানে ব্যবধান[i] একটি জোড়া আছে (left_i, right_i) ith ব্যবধানকে প্রতিনিধিত্ব করে যেটি left_i থেকে শুরু হয় এবং ডান_i (উভয়ই অন্তর্ভুক্ত) থেকে শেষ হয়। আমরা জিজ্ঞাসা নামক আরেকটি অ্যারে আছে. jth প্রশ্নের উত্তর হল ক্ষুদ্রতম ব্যবধানের আকার i যেমন left_i <=queries[j] <=right_i। যদি আমরা এই ধরনের ব্যবধান খুঁজে না পাই, তাহলে -1 ফেরত দিন। আমাদের প্রশ্নের উত্তর সম্বলিত একটি অ্যারে খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুটটি অন্তরের মত হয় =[[2,5],[3,5],[4,7],[5,5]] প্রশ্ন =[3,4,5,6], তাহলে আউটপুট হবে হতে [3, 3, 1, 4], কারণ প্রশ্নগুলি নিম্নরূপ প্রক্রিয়া করা হয় -
-
প্রশ্নের জন্য =3:ব্যবধান [3,5] হল সবচেয়ে ছোট যা 3 ধারণ করে। তাই, 5 - 3 + 1 =3।
-
প্রশ্নের জন্য =4:ব্যবধান [3,5] হল সবচেয়ে ছোট যেটি 4 ধারণ করে। তাই, 5 - 3 + 1 =3।
-
প্রশ্নের জন্য =5:ব্যবধান [5,5] হল সবচেয়ে ছোট যেটি 5 ধারণ করে। তাই, 5 - 5 + 1 =1।
-
প্রশ্নের জন্য =6:ব্যবধান [4,7] হল সবচেয়ে ছোট যেটি 6 ধারণ করে। তাই, 7 - 4 + 1 =4।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
intervals :=তালিকার ব্যবধানগুলিকে বিপরীত ক্রমে সাজান
-
h :=একটি নতুন তালিকা
-
res :=একটি নতুন মানচিত্র
-
প্রশ্নের সাজানো তালিকায় প্রতিটি q-এর জন্য, করুন
-
যখন ব্যবধান খালি নয় এবং শেষ ব্যবধানের শেষ সময় <=q, do
-
(i, j) :=ব্যবধান থেকে শেষ ব্যবধান, এবং এটি সরান
-
যদি j>=q হয়, তাহলে
-
স্তূপে জোড়া (j-i+1, j) সন্নিবেশ করান h
-
-
-
যদিও h খালি নয় এবং h
-
h
থেকে শীর্ষ উপাদান মুছুন
-
-
res[q] :=h এর সর্বোচ্চ ব্যবধানের শুরুর সময় যদি h খালি না হয় অন্যথায় -1
-
-
সমস্ত q প্রশ্নের জন্য res[q] তালিকা ফেরত দিন
উদাহরণ
আরও ভালোভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি
import heapq
def solve(intervals, queries):
intervals = sorted(intervals)[::-1]
h = []
res = {}
for q in sorted(queries):
while intervals and intervals[-1][0] <= q:
i, j = intervals.pop()
if j >= q:
heapq.heappush(h, [j - i + 1, j])
while h and h[0][1] < q:
heapq.heappop(h)
res[q] = h[0][0] if h else -1
return [res[q] for q in queries]
intervals = [[2,5],[3,5],[4,7],[5,5]]
queries = [3,4,5,6]
print(solve(intervals, queries)) ইনপুট
[[2,5],[3,5],[4,7],[5,5]], [3,4,5,6]
আউটপুট
[3, 3, 1, 4]
