Minimum Interval to Include Each Query

PracticeNeetCode ↗LeetCode ↗

Given a list of intervals and a list of query values, for each query find the size of the smallest interval that contains it (size = end − start + 1). If no interval contains a query, its answer is −1.

Example

Key Pointers

• Processing queries in increasing order lets intervals be added to a candidate pool incrementally, as the query value passes each interval's start — no rescanning every interval per query.
• A min-heap keyed by interval size means the smallest active candidate is always at the top, ready to check for each query.
• Intervals whose end has already fallen behind the current query are stale; pop them off the heap lazily instead of removing them eagerly.

Step-by-Step Analysis

1. Sort intervals by start time; sort query indices by their query value so the original answer order can be restored later.
2. Maintain a min-heap of (size, end) for intervals that have "started" relative to the current query.
3. For each query in increasing order, push every interval whose start is at or before the query into the heap.
4. Pop from the heap while its top interval's end is before the query — those intervals no longer cover it.
5. If the heap isn't empty, its top's size is the answer for this query; otherwise the answer is −1.
6. Write results back into the original query order using the saved indices.

Complexity

Time: O((n + q) log n) — Space: O(n + q)

Code

import heapq

def minInterval(intervals: list[list[int]], queries: list[int]) -> list[int]:
    intervals.sort()
    sorted_queries = sorted(range(len(queries)), key=lambda i: queries[i])

    heap = []
    result = [0] * len(queries)
    i = 0

    for qi in sorted_queries:
        q = queries[qi]
        while i < len(intervals) and intervals[i][0] <= q:
            start, end = intervals[i]
            heapq.heappush(heap, (end - start + 1, end))
            i += 1

        while heap and heap[0][1] < q:
            heapq.heappop(heap)

        result[qi] = heap[0][0] if heap else -1

    return result

Code Explanation

How the solution above works, piece by piece.

1. Sort intervals by start and process queries from smallest to largest (keeping their original positions for the answer).
2. For each query q, push every interval with start <= q onto a min-heap keyed by size.
3. Pop intervals whose end is before q; they can't contain this or any later query, so removing them is permanent.
4. The heap's top is now the smallest interval that contains q, or −1 if the heap is empty.
5. O((n + q) log n): each interval is pushed and popped once.

Visual Walkthrough

Running it on intervals = [[1, 4], [2, 4], [3, 6], [4, 4]], queries = [2, 3, 4, 5]:

Video Explanation

NeetCode — LeetCode 1851