মনে করুন rooms নামে একটি অ্যারে আছে। যেখানে rooms[i] একটি জোড়া [roomId_i, size_i] ধারণ করে যা একটি রুম নির্দেশ করে যার আইডি roomId_i এবং আকার size_i। সব রুম নম্বর ভিন্ন। আমাদের কাছে queries নামে আরেকটি অ্যারে আছে, যেখানে queries[j] একটি জোড়া [preferred_j, minSize_j] ধারণ করে। j-তম কোয়েরির উত্তর হল এমন একটি রুম নম্বর যাতে −
রুমটির আকার কমপক্ষে minSize_j, এবং
|id - preferred_j| ন্যূনতম।
এখন, যদি আবসোলিউট ডিফারেন্সে টাই হয়, তবে সবচেয়ে ছোট আইডি वाले রুম ব্যবহার করুন। যদি এমন কোনো রুম নেই, তবে -1 রিটার্ন করুন। সুতরাং আমাদের answer নামে একটি অ্যারে বের করতে হবে যার দৈর্ঘ্য queries-এর সমান এবং যেটি j-তম কোয়েরির উত্তর ধারণ করবে।
সুতরাং, যদি ইনপুট হয় rooms = [[2,2],[1,2],[3,2]] queries = [[3,1],[3,3],[5,2]], তবে আউটপুট হবে [3, -1, 3] কারণ
কোয়েরি [3,1] এর জন্য: রুম 3 সবচেয়ে নিকট কারণ |3 - 3| = 0, এবং এর আকার 2 কমপক্ষে 1, তাই উত্তর 3।
কোয়েরি [3,3] এর জন্য: আকার কমপক্ষে 3 এমন কোনো রুম নেই, তাই উত্তর -1।
কোয়েরি [5,2] এর জন্য: রুম 3 সবচেয়ে নিকট কারণ |3 - 5| = 2, এবং এর আকার 2 কমপক্ষে 2, তাই উত্তর 3।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব −
রুমগুলো আকার অনুযায়ী সর্ট করুন, আকার সমান হলে রুম আইডি অনুযায়ী
queries = ইন্ডেক্স i এবং জোড়া (qid, size) এর জন্য (qid, size, i) জোড়ার একটি তালিকা
কোয়েরিগুলো আকার অনুযায়ী রিভার্স অর্ডারে সর্ট করুন, আকার সমান হলে preferred অনুযায়ী, আবার সমান হলে ইন্ডেক্স অনুযায়ী
ans := queries-এর আকারের একটি অ্যারে -1 দিয়ে পূরণ
X := একটি নতুন তালিকা
প্রতিটি (qid, size, i) in queries-এর জন্য, করুন
যতক্ষণ rooms খালি নয় এবং rooms-এর লাস্ট আইটেমের আকার >= size, করুন
(idr, _) := rooms থেকে লাস্ট এলিমেন্ট মুছে দিন
idr ইনসার্ট করার পর X সর্ট করুন
যদি X খালি নয়, তবে
j := সূচক যেখানে qid ইনসার্ট করলে X সর্টেড থাকবে
যদি j == X-এর আকার হয়, তবে
ans[i] := X-এর লাস্ট এলিমেন্ট
অন্যথায় যখন j == 0 হয়, তবে
ans[i] := X[0]
অন্যথায়,
যদি X[j] - qid < qid - X[j-1], তবে
ans[i] := X[j]
অন্যথায়,
ans[i] := X[j-1]
ans রিটার্ন করুন
উদাহরণ
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন
import bisect
def solve(rooms, queries):
rooms.sort(key=lambda x: (x[1], x[0]))
queries = [(qid, size, i) for i, (qid, size) in enumerate(queries)]
queries.sort(key=lambda x: (x[1], x[0], x[2]), reverse=True)
ans = [-1] * len(queries)
X = []
for qid, size, i in queries:
while rooms and rooms[-1][1] >= size:
idr, _ = rooms.pop()
bisect.insort(X, idr)
if X:
j = bisect.bisect(X, qid)
if j == len(X):
ans[i] = X[-1]
elif j == 0:
ans[i] = X[0]
else:
if X[j] - qid < qid - X[j-1]:
ans[i] = X[j]
else:
ans[i] = X[j-1]
return ans
rooms = [[2,2],[1,2],[3,2]]
queries = [[3,1],[3,3],[5,2]]
print(solve(rooms, queries))
ইনপুট
[[2,2],[1,2],[3,2]], [[3,1],[3,3],[5,2]]
আউটপুট
[3, -1, 3]
