মনে করুন আমাদের কাছে ইন্টারভালের একটি তালিকা আছে, যেখানে intervals[i] একটি জোড়া (left_i, right_i) থাকে যা i-তম ইন্টারভালকে left_i থেকে শুরু হয়ে right_i-তে শেষ হয়ে (দউভয়ই ইনক্লুসিভ) প্রতিনিধিত্ব করে। আমাদের কাছে queries নামে আরেকটি অ্যারে আছে। j-তম কোয়েরির উত্তর হল সবচেয়ে ছোট ইন্টারভাল i-এর আকার যাতে left_i <= queries[j] <= right_i। যদি আমরা এমন ইন্টারভাল না পাই, তবে -1 রিটার্ন করুন। আমাদের কোয়েরিগুলোর উত্তরের একটি অ্যারে বের করতে হবে।
সুতরাং, যদি ইনপুট হয় intervals = [[2,5],[3,5],[4,7],[5,5]] queries = [3,4,5,6], তবে আউটপুট হবে [3, 3, 1, 4], কারণ কোয়েরিগুলো নিচেরভাবে প্রসেস হয় −
query = 3 এর জন্য: ইন্টারভাল [3,5] 3 ধারণ করার সবচেয়ে ছোটটি। সুতরাং, 5 - 3 + 1 = 3।
query = 4 এর জন্য: ইন্টারভাল [3,5] 4 ধারণ করার সবচেয়ে ছোটটি। সুতরাং, 5 - 3 + 1 = 3।
query = 5 এর জন্য: ইন্টারভাল [5,5] 5 ধারণ করার সবচেয়ে ছোটটি। সুতরাং, 5 - 5 + 1 = 1।
query = 6 এর জন্য: ইন্টারভাল [4,7] 6 ধারণ করার সবচেয়ে ছোটটি। সুতরাং, 7 - 4 + 1 = 4।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব −
intervals := intervals তালিকাটি রিভার্স অর্ডারে সর্ট করুন
h := একটি নতুন তালিকা (হিপ)
res := একটি নতুন ম্যাপ
queries-এর সর্ট করা তালিকাতে প্রতিটি q-এর জন্য, করুন
যতক্ষণ intervals খালি নয় এবং লাস্ট ইন্টারভালের এন্ড টাইম <= q, করুন
(i, j) := intervals থেকে লাস্ট ইন্টারভাল, এবং মুছে দিন
যদি j >= q হয়, তবে
হিপ h-এ জোড়া (j-i+1, j) ইনসার্ট করুন
যতক্ষণ h খালি নয় এবং h-র টপমোস্ট ইন্টারভালের এন্ড টাইম < q, করুন
h-র টপ এলিমেন্ট মুছে দিন
res[q] := h খালি না হলে h-র টপমোস্ট ইন্টারভালের স্টার্ট টাইম, অন্যথায় -1
queries-এ সব 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]
