Program to find minimum interval to include each query in Python

Suppose we have a list of intervals, where intervals[i] has a pair (left_i, right_i) represents the ith interval starting at left_i and ending at right_i (both inclusive). We also have another array called queries. The answer to the jth query is the size of the smallest interval i such that left_i <= queries[j] <= right_i. If we cannot find such interval, then return -1. We have to find an array containing the answers to the queries.

So, if the input is like intervals = [[2,5],[3,5],[4,7],[5,5]] queries = [3,4,5,6], then the output will be [3, 3, 1, 4], because The queries are processed as follows −

• for query = 3: The interval [3,5] is the smallest one holding 3. so, 5 - 3 + 1 = 3.

• for query = 4: The interval [3,5] is the smallest one holding 4. so, 5 - 3 + 1 = 3.

• for query = 5: The interval [5,5] is the smallest one holding 5. so, 5 - 5 + 1 = 1.

• for query = 6: The interval [4,7] is the smallest one holding 6. so, 7 - 4 + 1 = 4.

To solve this, we will follow these steps −

• intervals := sort the list intervals in reverse order

• h := a new list

• res := a new map

• for each q in the sorted list of queries, do

  • while intervals is not empty and end time of last interval <= q, do

    • (i, j) := last interval from intervals, and remove it

    • if j >= q, then

      • insert pair (j-i+1, j) into heap h

  • while h is not empty and end time of top most interval in h < q, do

    • delete top element from h

  • res[q] := start time of top most interval of h if h is not empty otherwise -1

• return a list of res[q] for all q in queries

Example

Let us see the following implementation to get better understanding

import heapq def solve(intervals, queries):    intervals = sorted(intervals)[::-1]    h = []    res = {}    for q in sorted(queries):       while intervals and intervals[-1][0] <= q:          i, j = intervals.pop() if j >= q: heapq.heappush(h, [j - i + 1, j]) while h and h[0][1] < q: heapq.heappop(h) res[q] = h[0][0] if h else -1 return [res[q] for q in queries] intervals = [[2,5],[3,5],[4,7],[5,5]] queries = [3,4,5,6] print(solve(intervals, queries))

Input

[[2,5],[3,5],[4,7],[5,5]], [3,4,5,6]

Output

[3, 3, 1, 4]