Problem Statement

You are given a 2D integer array intervals, where intervals[i] = [lefti, righti] describes the ith interval starting at lefti and ending at righti (inclusive). The size of an interval is defined as the number of integers it contains, or more formally righti - lefti + 1.

You are also given an integer array queries. The answer to the jth query is the size of the smallest interval i such that lefti <= queries[j] <= righti. If no such interval exists, the answer is -1.

Return an array containing the answers to the queries.

Additional information

• 1 <= intervals.length <= 10^5
• 1 <= queries.length <= 10^5
• intervals[i].length == 2
• 1 <= lefti <= righti <= 10^7
• 1 <= queries[j] <= 10^7

Example 1:

Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]

Output: [3,3,1,4]

Explanation: The queries are processed as follows:

• Query 2: The intervals containing 2 are [1,4] and [2,4]. The smallest is [2,4] with size 3.
• Query 3: The intervals containing 3 are [1,4], [2,4], and [3,6]. The smallest is [2,4] with size 3.
• Query 4: The intervals containing 4 are [1,4], [2,4], [3,6], and [4,4]. The smallest is [4,4] with size 1.
• Query 5: The interval containing 5 is [3,6]. The size is 4.

Example 2:

Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]

Output: [2,-1,4,6]

Explanation: The queries are processed as follows:

• Query 2: The intervals containing 2 are [2,3], [2,5], and [1,8]. The smallest is [2,3] with size 2.
• Query 19: None of the intervals contain 19.
• Query 5: The intervals containing 5 are [2,5] and [1,8]. The smallest is [2,5] with size 4.
• Query 22: The interval containing 22 is [20,25]. The size is 6.

Brute Force (Iterative Checking)

Intuition

The most direct way to solve this is to process each query one by one. For every single query, we can loop through the entire intervals array.

If we find that the query falls inside a specific interval (meaning left <= query <= right), we calculate the size of that interval. We keep track of the minimum size we have seen so far for that specific query. Once we check all intervals, we record the minimum size in our result array. If no interval contained the query, we record -1.

Algorithm

1. Initialize a res array of the same length as queries, filled with -1.
2. Loop through each query using enumerate to get both the index i and the q value.
3. For each query, initialize min_size to infinity (float("inf")).
4. Loop through every left, right pair in intervals.
5. If left <= q <= right:

• Calculate size = right - left + 1.
• Update min_size = min(min_size, size).

6. If min_size is not infinity, update res[i] = min_size.
7. Return res.

def min_interval(intervals: list[list[int]], queries: list[int]) -> list[int]:
    res = [-1] * len(queries)
    
    for i, q in enumerate(queries):
        min_size = float("inf")
        
        for left, right in intervals:
            if left <= q <= right:
                size = right - left + 1
                min_size = min(min_size, size)
                
        if min_size != float("inf"):
            res[i] = min_size
            
    return res

Time & Space Complexity

• Time complexity: O(N * Q)

• Reason: We iterate through all N intervals for every single one of the Q queries. Given the constraints (both N and Q can be up to 10^5), this will unequivocally cause a Time Limit Exceeded (TLE) error.

• Space complexity: O(Q)

• Reason: The resulting array res takes space proportional to the number of queries.

Min-Heap and Offline Queries - Optimal

Intuition

To optimize this, we can process the queries "offline" by sorting them! If we sort the queries from smallest to largest, we can also sort our intervals by their start times. This allows us to walk through both the queries and the intervals in a single coordinated sweep.

As we look at a query, we grab all intervals that have started before or exactly at this query's value. We throw them into a Min-Heap, ordering them by their size.

Because we process queries in increasing order, any interval that ends before our current query is now completely useless for this query and all future queries! We can simply pop these expired intervals off the top of the heap. Once the expired ones are gone, the interval sitting at the top of the Min-Heap is mathematically guaranteed to be the smallest valid interval for our current query.

Algorithm

1. Sort the intervals array by their start times.
2. Because sorting the queries destroys their original order (which we need for the final answer), create a sorted list of tuples (query_val, original_index).
3. Initialize an empty min_heap and an idx pointer starting at 0 for the intervals array.
4. Initialize a res array of size len(queries) filled with -1.
5. Iterate through the sorted queries:

• While idx is less than len(intervals) and the current interval starts before or exactly at the current query_val:

• Calculate the interval's size.

• Push a tuple (size, right_bound) into the min_heap.

• Increment idx.

• While the min_heap is not empty and the top interval's right_bound is less than query_val (it expired):

• Pop it from the heap!

• If the min_heap is not empty, the top element is our answer. Store its size in res[original_index].

6. Return res.

def min_interval(intervals: list[list[int]], queries: list[int]) -> list[int]:
    # Sort intervals based on starting point
    intervals.sort(key=lambda x: x[0])
    
    # Store queries with their original indices so we can place answers correctly
    sorted_queries = sorted([(q, i) for i, q in enumerate(queries)])
    
    min_heap = []
    res = [-1] * len(queries)
    idx = 0
    
    for q_val, original_i in sorted_queries:
        # Add all valid starting intervals to the heap
        while idx < len(intervals) and intervals[idx][0] <= q_val:
            left, right = intervals[idx]
            size = right - left + 1
            # Push (size, right_bound) to the Min-Heap
            heapq.heappush(min_heap, (size, right))
            idx += 1
            
        # Remove intervals that end before the current query value
        while min_heap and min_heap[0][1] < q_val:
            heapq.heappop(min_heap)
            
        # The top of the heap is the smallest valid interval
        if min_heap:
            res[original_i] = min_heap[0][0]
            
    return res

Time & Space Complexity

• Time complexity: O(N log N + Q log Q)

• Reason: Sorting the intervals takes O(N log N) time, and sorting the queries takes O(Q log Q) time. Pushing and popping N intervals from the heap takes O(N log N). Overall, the time complexity is bounded by the sorting operations.

• Space complexity: O(N + Q)

• Reason: The min_heap can store up to N intervals. We also allocate auxiliary space to store the sorted_queries of size Q and the res array of size Q.