Minimum Interval to Include Each Query LeetCode solution in Python

1
class Solution:
2
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
3

4
        # sort queries from small to large
5
        q = deque(sorted([(x, i) for i, x in enumerate(queries)]))
6

7
        # answer to queries, initial state set to -1
8
        ans = [-1] * len(queries)
9

10
        # sort intervals by low, high and size
11
        ivals = deque(sorted([(a, b, b - a + 1) for a, b in intervals]))
12

13
        # available intervals
14
        cands = []
15

16
        while q:
17
            x, i = q.popleft()
18

19
            # if lower bound of intervals on the top of stack <= current query
20
            while ivals and x >= ivals[0][0]:
21
                a, b, c = ivals.popleft()
22
                # if higher bound of intervals also meets the requirements
23
                # if not then discard the interval
24
                if x <= b:
25
                    heappush(cands, (c, b, a))
26

27
            # udpate available intervals by removing old ones which no longer has a eligible higher bound
28
            while cands:
29
                c, b, a = heappop(cands)
30
                if x <= b:
31
                    ans[i] = c
32
                    heappush(cands, (c, b, a))
33
                    break
34

35
        return ans