LC 1851 [H] Minimum Interval to Include Each Query - ALawliet/algorithms GitHub Wiki

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        # O(nlogn + qlogq)
        intervals.sort() # O(nlogn)
        
        minHeap = []
        res = {} # hashmap to store original order of queries before sorting it then convert it back to list for end result
        i = 0
        
        for q in sorted(queries): # O(qlogq)
            while i < len(intervals) and intervals[i][0] <= q:
                l, r = intervals[i]
                heappush(minHeap, (r - l + 1, r))
                i += 1
                
            while minHeap and minHeap[0][1] < q:
                heappop(minHeap)
            res[q] = minHeap[0][0] if minHeap else -1
        
        return [res[q] for q in queries]