Problem Statement

Minimum Interval to Include Each Query

You are given a list of intervals and a list of queries. An interval is just a range, like [1, 4], which covers every number from 1 to 4. A query is a single number. For each query, you want the smallest interval that still covers that number. "Smallest" means the shortest range, measured as right minus left, plus one. If no interval covers the query, the answer is -1. The tool that makes this fast is a min-heap. A min-heap is like a magic bucket of numbers where the smallest one always floats to the top. You can throw new numbers in, and you can pull the smallest one out, and both stay quick. That fits here because, at any moment, we want the smallest interval covering the current query, and the heap hands us the smallest item without us searching the whole pile. The plan: sort the intervals by their left edge and sort the queries from smallest to largest. Then walk through the queries one at a time. As the query grows, add every interval that has started (its left edge is at or below the query) into the heap, sized by how wide it is. Before reading the answer, throw away any interval that has already ended (its right edge is below the query), since it no longer covers the number. Whatever sits on top of the heap is the smallest interval that still fits.

hardHeapSortingHeap / Priority QueueTime: O((n+q) log n) · Space: O(n+q)

Signals to notice

smallest interval containing each querysort and sweepheap for active intervals

Brute force first

For each query check all intervals — O(nm).

The key insight

Sort intervals by start, queries by value. Sweep: add intervals starting ≤ query to min-heap (by size). Remove expired. Heap top = answer. O((n+m) log n).

Trace it on `intervals=[[1,4],[2,4],[3,6],[4,4]], queries=[2,3,4,5]`

sort: intervals=[[1,4],[2,4],[3,6],[4,4]], queries by value=[(0,2),(1,3),(2,4),(3,5)], heap={}, i=0
q=2: push [1,4]->(4,4), [2,4]->(3,4); i=2; no expired (right>=2); heap top size=3 -> result[0]=3
q=3: push [3,6]->(4,6); i=3; no expired; heap={(3,4),(4,4),(4,6)}; top size=3 -> result[1]=3
q=4: push [4,4]->(1,4); i=4; no expired (all right>=4); heap={(1,4),(3,4),(4,4),(4,6)}; top size=1 -> result[2]=1
q=5: nothing to push; pop expired right<5: (1,4),(3,4),(4,4); heap={(4,6)}; top size=4 -> result[3]=4
return result=[3,3,1,4]

What must stay true

Sweep ensures each interval added/removed once. Min-heap by interval size gives smallest valid interval.

Shape of the loop

sort intervals by left; sort queries by value (keep original index)
for each (idx, q) in sorted queries:
    while next interval.left <= q: push (size, right) onto min-heap
    while heap.top.right < q: pop heap   # drop expired
    if heap: result[idx] = heap.top.size
return result

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not removing expired intervals — those ending before the query are invalid.

Heap / Priority Queue Pattern