For query 2, the intervals containing it are [1,4] (length 4) and [2,4] (length 3), so the answer is 3.
Restating the Problem: You are given intervals and a list of queries. For each query point, you need to find the interval that envelops that point and has the smallest total length.
Constraints to note: Up to 100,000 intervals and 100,000 queries. This confirms O(n^2) is impossible. We need an O(n \log n) approach.
Edge cases: A query might not fall into any interval, in which case we return -1. Multiple queries might ask for the same point.
Checking every interval for every query is O(n \times q) — ten billion operations here. Far too slow.
Three ideas combine to fix it, and each one is worth naming separately.
Idea 1 — answer the queries out of order. Nothing says you must answer them in the order given. Sort the queries, answer them in increasing order, and put the answers back into their original positions at the end. That is called offline query processing, and it is the key that unlocks everything else: sorted queries mean you can sweep the intervals forwards and never go back.
Idea 2 — sort the intervals by start, and add them as the queries advance. When processing query q, every interval with start <= q is a candidate. Because the queries only increase, the set of candidates only grows — so each interval is added exactly once across the whole run.
Idea 3 — a min-heap keyed by length gives the shortest candidate. But some candidates have already ended before the current query, so before reading the heap's top you must discard anything with end < q.
That last step is the subtle one, and it works because the queries increase: an interval that has expired for this query has expired for every later one too, so it can be removed permanently.
import heapqclass Solution: def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]: intervals.sort() # (1) by start answer = {} # (2) heap = [] # (3) (length, end) i = 0 for q in sorted(queries): # (4) queries in order # 1. every interval that has started is a candidate while i < len(intervals) and intervals[i][0] <= q: # (5) start, end = intervals[i] heapq.heappush(heap, (end - start + 1, end)) # (6) i += 1 # 2. discard candidates that have already finished while heap and heap[0][1] < q: # (7) heapq.heappop(heap) # 3. the top is the shortest interval still covering q answer[q] = heap[0][0] if heap else -1 # (8) return [answer[q] for q in queries] # (9) restore the original order
ts
function minInterval(intervals: number[][], queries: number[]): number[] { intervals.sort((a, b) => a[0] - b[0]); // (1) const answer = new Map<number, number>(); // (2) const heap = new MinHeap<[number, number]>((e) => e[0]); // (3) [length, end] let i = 0; for (const q of [...queries].sort((a, b) => a - b)) { // (4) while (i < intervals.length && intervals[i][0] <= q) { // (5) const [s, e] = intervals[i++]; heap.push([e - s + 1, e]); // (6) } while (heap.size && heap.peek()![1] < q) heap.pop(); // (7) answer.set(q, heap.size ? heap.peek()![0] : -1); // (8) } return queries.map(q => answer.get(q)!); // (9)}
(2) The answers, keyed by query value, so they can be put back in the original order at the end.
(3) A min-heap of (length, end) for intervals that have started. The shortest one sits at the front.
(4) Answer the queries in increasing order. This is the trick that makes the problem fast. As the query value only grows, each interval only needs to be added once and removed once. Answering questions in an order you choose, rather than the order asked, is called offline processing.
(5) Every interval that starts at or before q could cover it.
(6) Add it to the heap with its length, end − start + 1. Both ends count, so the interval [2, 4] has length 3.
(7) Remove intervals that end before q. They cannot cover this query, and because later queries are even bigger, they never will. Only the front of the heap needs checking: an expired interval further back does no harm until it reaches the front.
(8) The front of the heap is the shortest interval covering q, or −1 if none does.
(9) Put the answers back in the order the queries were asked.
Four details.
The heap is keyed by length, with the end stored alongside. You want the shortest, so length is the priority; the end is needed for the expiry check.
while heap[0][1] < q uses a while, not an if. Several intervals may have expired since the last query.
Expired intervals are removed permanently, and that is what keeps the total work linear in the number of intervals. Each interval is pushed once and popped at most once — the same amortized argument as the monotonic stack in 4.8.
Code Walkthrough:
Sorting Inputs: We first sort the intervals by their start times.
Offline Queries: We process the queries in ascending sorted order, so we can sweep through the intervals left to right without backtracking.
Tracking Candidates (while intervals[i][0] <= q): For the current query q, we push all intervals that start at or before q into a Min-Heap. The heap prioritizes intervals by their length (end - start + 1).
Pruning Expired (while heap[0][1] < q): Before picking an answer, we must discard intervals from the top of the heap if they have already ended before q. We permanently pop them.
Recording Answers: The valid interval at the top of the heap is the shortest one covering q. We store this in a hash map answer.
Restoring Order: We build the final output by mapping the original queries array through our answer hash map.
A dictionary maps each query value to its answer, then the final list comprehension restores the original order. This also handles duplicate queries for free, since the same value maps to the same answer.
O((n + q) \log n) — sorting both lists, then each interval pushed and popped at most once with each heap operation O(\log n).
O(n + q) space.
Time Complexity:O(n \log n + q \log q). Sorting the intervals takes O(n \log n) and sorting queries takes O(q \log q). Inside the loop, every interval is pushed to the heap exactly once and popped at most once, contributing O(n \log n). Total time is O(n \log n + q \log q).
Space Complexity:O(n + q) to store the heap, the hash map for answers, and the sorted arrays.
When queries can be answered in any order, sorting them is often what makes a problem tractable.
The catch is that you must have all the queries up front. It does not work if they arrive one at a time and each must be answered immediately. This distinction has a name: offline versus online.
Other problems built on it:
Range queries with union-find — process edges and queries together in weight order.
Counting smaller elements after self — merge sort or a Fenwick tree, answering as you go.
Kth smallest in a range — sort queries by right endpoint and sweep.
If a problem looks impossible online, ask whether it becomes easy offline. That question is the whole technique.
If the queries had to be answered online, you would need a different structure — a segment tree or an interval tree over the coordinate range, giving O(\log n) per query with O(n \log n) preprocessing. 4.13.4 builds segment trees.
More code, and unnecessary here because the queries are all given in advance. Naming it as the online answer is a good way to close.
"Why can you reorder the queries?" Each answer is independent, so only the output order matters, and a dictionary restores it.
"Why does the heap need the end as well as the length?" To detect intervals that have expired.
"Why is the expiry removal permanent?" Queries only increase, so an expired interval never becomes relevant again.
"Why is this O((n+q)\log n) and not worse?" Each interval is pushed once and popped once across the whole run.
"What if the queries were online?" A segment tree or interval tree.
"What about duplicate queries?" The dictionary handles them with no extra work.
One thing to volunteer: name offline processing as the technique and say what it costs — all queries must be known in advance. Recognising a problem as offline-solvable is a genuinely senior observation and it is what makes this Hard problem approachable.
Next:4.28 covers the problems where the trick is arithmetic or index manipulation rather than a data structure.