TL;DR
Sort intervals and queries, sweep with a min-heap keyed by interval size — O(n log n + q log q) time, O(n + q) space.
Approach 1 — Brute force: scan all intervals per query
For each query, walk the whole interval list, track the smallest size among intervals that contain it.
from typing import List
def minInterval(
self, intervals: List[List[int]], queries: List[int]
) -> List[int]:
answers: List[int] = []
for q in queries:
best = -1
for left, right in intervals:
if left <= q <= right:
size = right - left + 1
if best == -1 or size < best:
best = size
answers.append(best)
return answers
Complexity: O(n * q) time, O(q) space for the output.
With n = q = 10^5 that is ~10^10 containment checks, far too slow. Consecutive queries mostly see the same set of containing intervals, but the brute force rediscovers that set from scratch every time.
Approach 2 — Sort both + min-heap keyed by size (offline sweep)
Answer the queries offline: process them in ascending order and restore the original order at the end. Because the query value only grows, each interval has a simple life cycle. It enters consideration when the query reaches its left end, and it is dead once the query passes its right end. Sweep queries in increasing order, admit intervals by left endpoint with a pointer, and keep the live ones in a min-heap ordered by size. Dead intervals need no eager cleanup: discard them lazily, popping while the heap’s top has right < q. An interval buried deeper in the heap is evicted only when it reaches the top.
Storing (size, right) in the heap keeps the smallest live candidate at the top, with its right available for the death test.
For each query, the loop admits, evicts, then reads the answer:
flowchart TD
A[Next query q in sorted order] --> B{Next interval left <= q?}
B -- yes --> C[Push size, right onto min-heap]
C --> B
B -- no --> D{Heap top right < q?}
D -- yes --> E[Pop dead interval]
E --> D
D -- no --> F[Answer = heap top size, or -1 if empty]
F --> A
import heapq
from typing import List
def minInterval(
self, intervals: List[List[int]], queries: List[int]
) -> List[int]:
intervals.sort(key=lambda it: it[0])
answer_for: dict[int, int] = {}
heap: List[tuple[int, int]] = [] # (size, right) of live intervals
i, n = 0, len(intervals)
for q in sorted(set(queries)):
# Admit every interval that has started by q.
while i < n and intervals[i][0] <= q:
left, right = intervals[i]
heapq.heappush(heap, (right - left + 1, right))
i += 1
# Lazily evict intervals that ended before q.
while heap and heap[0][1] < q:
heapq.heappop(heap)
answer_for[q] = heap[0][0] if heap else -1
return [answer_for[q] for q in queries]
Deduplicating with sorted(set(queries)) and a dict handles repeated queries: the same value always has the same answer. The final list comprehension restores the input order.
Walkthrough on intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]:
Sorted intervals: [[1,8],[2,3],[2,5],[20,25]]. Sorted unique queries: [2, 5, 19, 22].
q = 2: admit [1,8] (size 8), [2,3] (size 2), [2,5] (size 4). Heap top is (2, 3); 3 >= 2, alive → answer 2.q = 5: nothing new to admit (20 > 5). Top (2, 3) has 3 < 5 → pop. New top (4, 5) has 5 >= 5, alive → answer 4.q = 19: nothing to admit. Top (4, 5) dead → pop; (8, 8) dead → pop. Heap empty → answer -1.q = 22: admit [20,25] (size 6). Top (6, 25) alive → answer 6.- Map back to original order
[2, 19, 5, 22] → [2, -1, 4, 6]. Matches the expected output.
Complexity: sorting costs O(n log n + q log q); across the entire sweep each interval is pushed once and popped at most once (O(n log n) heap work total, thanks to the lazy deletion). Total O((n + q) log(n + q)) time, O(n + q) space.
Variant worth knowing: the same offline idea works with a sorted list of interval sizes plus binary-searchable events, or with a segment tree over coordinates (“paint” each interval’s range with min-size). The heap sweep is the version interviewers expect; it needs the least machinery for the same bound.
Common pitfalls
- Evicting dead intervals before admitting new ones is fine, but answering before evicting is not — the heap top must be validated against the current
q right before you read it.
- Keying the heap by
right (end time) instead of by size. The question at the top of the heap is “smallest size still alive?”, so size must be the primary key; right is stored only for the death test.
- Forgetting to restore the original query order (or mishandling duplicate queries) — the sweep requires sorted queries, but the caller expects answers positionally.
- Computing size as
right - left instead of right - left + 1 — these are closed intervals; [4,4] has size 1, not 0.
- Popping dead intervals with
heap[0][1] <= q — an interval whose right end equals the query still contains it; the eviction test is strictly <.
Pattern takeaway
When many queries hit the same set of intervals, go offline: sort the queries, sort the intervals, and sweep once, admitting intervals with a pointer and retiring them lazily from a heap. The heap’s sort key should be the quantity the question asks to minimize (here interval size), while the sweep’s own ordering handles time. This admit/expire sweep generalizes to most “for each query, best interval covering it” problems.