कमरों की सूची (roomId, size) और क्वेरीज़ (preferred, minSize) दी गई हैं। प्रत्येक क्वेरी के लिए: आकार ≥ minSize वाला कमरा खोजें जिसका |roomId - preferred| न्यूनतम हो। टाई में छोटी roomId चुनें। ऐसा कमरा न हो तो -1।
एल्गोरिदम: ऑफलाइन प्रोसेसिंग + बाइनरी सर्च
- कमरों को आकार के अनुसार आरोही क्रम में सॉर्ट करें
- क्वेरीज़ को (preferred, minSize, index) में बदलें और minSize के अनुसार अवरोही क्रम में सॉर्ट करें
- सॉर्टेड कंटेनर (बाइनरी सर्च के लिए सॉर्टेड सूची) में योग्य कमरे जोड़ें
- प्रत्येक क्वेरी के लिए बाइनरी सर्च से निकटतम roomId खोजें
Python कार्यान्वयन
import bisect
def closest_room(rooms, queries):
# कमरे: आकार द्वारा आरोही, टाई में roomId द्वारा
rooms.sort(key=lambda x: (x[1], x[0]))
# क्वेरीज़: (preferred, minSize, original_index)
queries = [(qid, size, i) for i, (qid, size) in enumerate(queries)]
# minSize अवरोही, टाई में preferred, फिर index
queries.sort(key=lambda x: (x[1], x[0], x[2]), reverse=True)
ans = [-1] * len(queries)
sorted_ids = [] # सॉर्टेड roomIds (bisect के लिए)
for qid, size, i in queries:
# सभी कमरे जिनका आकार ≥ size, sorted_ids में डालें
while rooms and rooms[-1][1] >= size:
room_id, _ = rooms.pop()
bisect.insort(sorted_ids, room_id)
if sorted_ids:
# बाइनरी सर्च: qid डालने की स्थिति
j = bisect.bisect(sorted_ids, qid)
if j == len(sorted_ids):
# सभी roomId < qid, सबसे बड़ा चुनें
ans[i] = sorted_ids[-1]
elif j == 0:
# सभी roomId > qid, सबसे छोटा चुनें
ans[i] = sorted_ids[0]
else:
# दोनों तरफ उम्मीदवार, निकटतम चुनें
left = sorted_ids[j-1]
right = sorted_ids[j]
if right - qid < qid - left:
ans[i] = right
else:
ans[i] = left # टाई में छोटा (left)
return ans
# परीक्षण
rooms = [[2,2], [1,2], [3,2]]
queries = [[3,1], [3,3], [5,2]]
print(closest_room(rooms, queries)) # [3, -1, 3]
व्याख्या
| क्वेरी | योग्य कमरे (size≥minSize) | निकटतम preferred | उत्तर |
|---|---|---|---|
| [3,1] | सभी (size=2≥1) | room 3 (|3-3|=0) | 3 |
| [3,3] | कोई नहीं (सभी size=2<3) | - | -1 |
| [5,2] | सभी (size=2≥2) | room 3 (|3-5|=2) | 3 |
जटिलता
- समय: O((n + q) log n) - सॉर्टिंग + बाइनरी सर्च/इन्सर्ट
- स्थान: O(n + q)
मुख्य बिंदु
- कमरों और क्वेरीज़ दोनों को सॉर्ट करके "ऑफलाइन" प्रोसेसिंग
bisect.insortसॉर्टेड सूची बनाए रखता है O(log n) इन्सर्ट मेंbisect.bisectइन्सर्शन पॉइंट देता है O(log n)- बड़े इनपुट के लिए रैखिक स्कैन से बहुत तेज़