मान लीजिए कि हमारे पास अंतराल की एक सूची है, जहां अंतराल [i] में एक जोड़ी है (बाएं_आई, दाएं_आई) ith अंतराल का प्रतिनिधित्व करता है जो बाएं_आई से शुरू होता है और दाएं_आई (दोनों समावेशी) पर समाप्त होता है। हमारे पास क्वेरीज़ नामक एक और सरणी भी है। jth क्वेरी का उत्तर सबसे छोटे अंतराल का आकार है i जैसे कि left_i <=query[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।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
अंतराल :=सूची अंतरालों को उल्टे क्रम में क्रमबद्ध करें
-
h:=एक नई सूची
-
रेस :=एक नया नक्शा
-
प्रश्नों की क्रमबद्ध सूची में प्रत्येक q के लिए, करें
-
जबकि अंतराल खाली नहीं है और अंतिम अंतराल का अंत समय <=q, करें
-
(i, j) :=अंतराल से अंतिम अंतराल, और इसे हटा दें
-
अगर j>=q, तो
-
जोड़ी (j-i+1, j) को हीप 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]