4.27.6 — Minimum Interval to Include Each Query

LeetCode 1851 · Hard

The problem

For each query value, find the shortest interval that contains it, and return that interval's length. Return -1 if no interval contains the query.

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

For query 2, the intervals containing it are [1,4] (length 4) and [2,4] (length 3), so the answer is 3.

Up to 100,000 intervals and 100,000 queries.

The pattern

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.

The solution

PythonTypeScript

python

import heapq

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        intervals.sort()                                   # by start
        answer = {}
        heap = []                                          # (length, end)
        i = 0

        for q in sorted(queries):                          # queries in order
            # 1. every interval that has started is a candidate
            while i < len(intervals) and intervals[i][0] <= q:
                start, end = intervals[i]
                heapq.heappush(heap, (end - start + 1, end))
                i += 1

            # 2. discard candidates that have already finished
            while heap and heap[0][1] < q:
                heapq.heappop(heap)

            # 3. the top is the shortest interval still covering q
            answer[q] = heap[0][0] if heap else -1

        return [answer[q] for q in queries]                # restore the original order

function minInterval(intervals: number[][], queries: number[]): number[] {
  intervals.sort((a, b) => a[0] - b[0]);
  const answer = new Map<number, number>();
  const heap = new MinHeap<[number, number]>((e) => e[0]);   // [length, end]
  let i = 0;

  for (const q of [...queries].sort((a, b) => a - b)) {
    while (i < intervals.length && intervals[i][0] <= q) {
      const [s, e] = intervals[i++];
      heap.push([e - s + 1, e]);
    }

    while (heap.size && heap.peek()![1] < q) heap.pop();

    answer.set(q, heap.size ? heap.peek()![0] : -1);
  }

  return queries.map(q => answer.get(q)!);
}

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.

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.

Trace

intervals = [[1,4],[2,4],[3,6],[4,4]], sorted queries [2,3,4,5].

q	intervals added	expired removed	heap top	answer
2	`[1,4]` len 4, `[2,4]` len 3	none	(3, 4)	3
3	`[3,6]` len 4	none	(3, 4)	3
4	`[4,4]` len 1	none	(1, 4)	1
5	none	(1,4), (3,4), (4,4) all end < 5	(4, 6)	4

[3,3,1,4] ✓.

Query 5 is the interesting one — three candidates expire at once, which is why the removal loop is a while.

Complexity

$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.

Offline processing, as a technique

When queries can be answered in any order, sorting them is often what makes a problem tractable.

The trade is that you must have all the queries up front — this does not work if they arrive one at a time and each must be answered immediately. That distinction, offline versus online, is worth knowing by name.

The alternative structures

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.

What the interviewer will push on

"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.

4.27.6 — Minimum Interval to Include Each Query ​

The problem ​

The pattern ​

The solution ​

Trace ​

Complexity ​

Offline processing, as a technique ​

The alternative structures ​

What the interviewer will push on ​