Hard- 1851. Minimum Interval to Include Each Query

题意:给定一个二维阵列表示区间[left, right]\(表示left, right两个数字)，区间的长度定义为right - left + 1
另给定一个阵列表示query，要回答每个query包含该数字的最小长度为何?
Sample Input:intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
说明: 
- Query = 2: [2,4] 是最小的区间包含 2，故答案为 4 - 2 + 1 = 3
- Query = 3: [2,4] 是最小的区间包含 3，故答案为 4 - 2 + 1 = 3
- Query = 4: [4,4] 是最小的区间包含 4，故答案为 4 - 4 + 1 = 1
- Query = 5: [3,6] 是最小的区间包含 5，故答案为 6 - 3 + 1 = 4.

本题需要事先将queries和intervals排序，
每次进来一个新的query时，将旧的元素踢除(区间右界小於现在的query)，
尝试加入新的可能元素(区间左界小於现在的query)，
由於需要一直新增、移除元素，
还要查询最小值，故想到用「heap」结构

# 1851. Minimum Interval to Include Each Query 题解
from heapq import heappop, heappush
class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        A = sorted(intervals)
        Q = sorted((q, i) for i, q in enumerate(queries))
        heap = []
        res = [-1] * len(Q)
        j = 0
        
        for query, idx in Q:
            while heap and heap[0][1] < query:
                heappop(heap)
            while j < len(A) :
                left, right = A[j]
                if left>query:
                    break
                if right>=query:
                    heappush(heap, (right - left + 1, right))
                j+=1
            if heap:
                res[idx] = heap[0][0]
        return res