1851. Minimum Interval to Include Each Query

class Solution:
    def minInterval(self, intervals: list[list[int]], queries: list[int]) -> list[int]:
        left = intervals[:]

        # Sorting the intervals by the left
        left.sort()

        tq = []
        for i, n in enumerate(queries):
            tq.append((n, i))
        
        tq.sort(key=lambda x: x[0])

        output = [-1] * len(queries)

        h = []

        heapq.heapify(h)


        # keeping track o fthe current interval index that is already in the heap, since we can reuse the intervals for each selecrtion of the intevals for the queryies
        interval_idex = 0

        for j in tq:
            q, idex = j

            while interval_idex < len(left) and left[interval_idex][0] <= q:
                size = left[interval_idex][1] - left[interval_idex][0] + 1
            
                heapq.heappush(h, (size, left[interval_idex][0], left[interval_idex][1]))

                interval_idex += 1


            while len(h) > 0 and h[0][2] < q:
                heapq.heappop(h)
            
            
            if len(h) > 0:
                output[idex] = h[0][0]

        return output

Here is the solution to the problem.The flow of this code: we know that we need to find the range of intervals that match the current query, in the following format:

left <= qi <= right

So we first sort the queries, and since we need to know the index of each query, we also keep track of the index so we can reference it when we backfill it with the answer. Then we also sort the intervals by the start time (left). This means the start times will be increasing as we look for intervals that are a good fit for our query. We can make sure that as long as the start time is less than or equal to q, we should be good, and we know when to stop.

As you can see, we are going through the new sorted query list tq. As we go through it, we check through the list of intervals to see if the current left is within scope, which means less than or equal to q. If it is, we queue up the item with the size as the measuring metric, and the left and right as secondary values.

We also increase the interval index, keeping track of which intervals are already in the heap queue that we are making.

Of course, we don’t dump every single interval into the heap queue all at once. We only add an interval when it comes into scope for the current query, and since the queries are sorted, it stays available for future queries too.

Then we pop the ones on the top of the heap queue that have a right value less than the query number.

And of course, we keep the default value of the output (answer) array as -1 in case there aren’t any intervals that satisfy the conditions. So we have a check in place to see if there are any items in the heap queue. If there are, we use the top one, and with the index we kept track of, we place the size in the spot where we expect the minimal interval.

runtime: runtime query * log query + intervals * log intervals