Python में प्रत्येक क्वेरी को शामिल करने वाला न्यूनतम अंतराल ज्ञात करें

दिए गए अंतरालों की सूची और क्वेरीज़ के लिए, प्रत्येक क्वेरी को शामिल करने वाला सबसे छोटा अंतराल खोजें। अंतराल [left, right] क्वेरी q को शामिल करता है यदि left ≤ q ≤ right। आकार = right - left + 1।

एल्गोरिदम: स्वीप लाइन + मिन-हीप

1. अंतरालों को आरंभ बिंदु के अनुसार अवरोही क्रम में सॉर्ट करें
2. क्वेरीज़ को आरोही क्रम में सॉर्ट करें
3. प्रत्येक क्वेरी के लिए (क्रम में):
   • वे सभी अंतराल हीप में डालें जिनका left ≤ q
   • हीप से वे अंतराल हटाएं जिनका right < q (क्वेरी शामिल नहीं करते)
   • हीप में न्यूनतम आकार वाला अंतराल उत्तर है

Python कार्यान्वयन

import heapq

def min_interval(intervals, queries):
    # अंतरालों को left के अनुसार अवरोही क्रम में सॉर्ट (पॉप के लिए)
    intervals = sorted(intervals)[::-1]
    
    # मिन-हीप: (आकार, right)
    heap = []
    # परिणाम मैप
    res = {}
    
    # क्वेरीज़ को सॉर्टेड क्रम में प्रोसेस करें
    for q in sorted(queries):
        # सभी अंतराल जिनका left ≤ q, हीप में डालें
        while intervals and intervals[-1][0] <= q:
            i, j = intervals.pop()
            if j >= q:  # केवल यदि right ≥ q (क्वेरी शामिल करता है)
                heapq.heappush(heap, (j - i + 1, j))
        
        # हीप से वे अंतराल हटाएं जिनका right < q
        while heap and heap[0][1] < q:
            heapq.heappop(heap)
        
        # उत्तर: हीप में न्यूनतम आकार या -1
        res[q] = heap[0][0] if heap else -1
    
    # मूल क्वेरी क्रम में परिणाम लौटाएं
    return [res[q] for q in queries]

# परीक्षण
intervals = [[2,5], [3,5], [4,7], [5,5]]
queries = [3, 4, 5, 6]
print(min_interval(intervals, queries))  # [3, 3, 1, 4]

व्याख्या

जटिलता

• समय: O((n + q) log n) - सॉर्टिंग + हीप ऑपरेशन्स
• स्थान: O(n + q)

मुख्य बिंदु

• क्वेरीज़ को सॉर्ट करने से स्वीप लाइन संभव होती है
• मिन-हीप स्वचालित रूप से न्यूनतम आकार वाला वैध अंतराल शीर्ष पर रखता है
• (size, right) टपल: size से मिन-हीप ऑर्डर, right से एक्सपायर जांच
• ऑफलाइन क्वेरी प्रोसेसिंग पैटर्न