Intervals crash course ↗ · 112

1851. Minimum Interval to Include Each Query

Sort the intervals by start and process queries in sorted order. A min-heap keyed by interval size lazily admits intervals that could cover the current query and evicts those that already ended — the heap top is always the smallest valid answer.

● HardSortingMin-Heap / Priority QueueOffline QueriesTypeScript

PROBLEM What we're solving

You have a list of intervals [[start, end], …] and a list of integer queries. For each query q, find the size (i.e. end − start + 1) of the smallest interval that contains q. An interval [a, b] contains q when a ≤ q ≤ b. If no interval covers q, answer -1 for that query.

Concrete example: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5] → answer [3,3,1,4].

  • q=2: covered by [1,4] (size 4), [2,4] (size 3). Smallest size = 3.
  • q=3: covered by [1,4], [2,4], [3,6]. Smallest = 3.
  • q=4: also covered by [4,4] (size 1). Smallest = 1.
  • q=5: only [3,6] (size 4). Answer = 4.

KEY IDEA Sort both, sweep with a min-heap that self-evicts expired intervals

Insight → If you sort queries andintervals by value/start, you can add intervals to a min-heap exactly once (when their start ≤ current query) and remove them lazily (when their end < current query). The heap is keyed by interval size, so the heap top is always the smallest interval that still contains the current query — no scan needed. This is the offline query pattern: re-order the queries to exploit sorted structure, then restore original indices at the end.

RECIPE Sort, sweep, push valid, pop expired, read top

  • 1 · Sort intervals by start. This lets us add intervals to the heap incrementally — each interval is encountered exactly once as the query pointer advances.
  • 2 · Sort queries (keeping original indices). Wrap each query as [value, originalIndex] and sort by value. Answers go back into result[originalIndex] at the end.
  • 3 · For each sorted query q:
    • Push every interval with start ≤ q onto a min-heap keyed by size = end − start + 1. Store [size, end] — we need end for eviction.
    • Evict all heap entries with end < q: those intervals ended before qso they can't cover it.
    • Read.If the heap is non-empty, the top entry's size is the answer (smallest valid interval).
  • 4 · Return the result array in original query order.
Classic confusion → forgetting to key the heap on size and instead keying on end. If you key by end, the top will be the interval that expires soonest — not the smallest one. You must push [size, end] so the min-heap orders by size (what the problem asks) while still letting you check end for expiry. Many solutions get this backwards on first attempt.

COST Complexity & alternatives

Brute force (for each query, scan all intervals)
O(n · q)
No structure; re-scans everything per query.
Sort + offline min-heap
O((n + q) log n)
Each interval pushed and popped at most once; query sort is O(q log q).

Every interval is pushed once and popped at most once — the heap never grows beyond n entries. The eviction loop looks like it could be slow but across all queries each entry is popped at most once: amortised O(1) per eviction, O(n log n) total. Space: O(n) for the heap + O(q) for the answer array.

Pattern transfer → the same offline-query + event-sweep skeleton powers Falling Squares (LC 699), Skyline Problem(LC 218), and any problem where a set of "active" ranges must answer point queries. Also related to Meeting Rooms II (LC 253) — both use a heap to manage a changing set of live intervals.

RUN IT Sort + min-heap: smallest interval covering each query

step 0 / 15
STARTSort intervals by start: [1,4], [2,4], [3,6], [4,4]. Sort queries (with original indices): 2(i=0), 3(i=1), 4(i=2), 5(i=3). Process each query in ascending order.
1function minInterval(intervals: number[][], queries: number[]): number[] {
2  // Sort intervals by start value so we can add them lazily as queries grow
3▶  intervals.sort((a, b) => a[0] - b[0]);
4 
5  // Process queries in ascending order, then restore original positions
6▶  const indexedQueries = queries.map((q, i) => [q, i] as [number, number]);
7▶  indexedQueries.sort((a, b) => a[0] - b[0]);
8 
9▶  const result: number[] = new Array(queries.length).fill(-1);
10 
11  // Min-heap keyed by interval size: [size, end]
12▶  const heap: [number, number][] = [];
13▶  let ivIdx = 0;
14 
15  const heapPush = (entry: [number, number]) => {
16    heap.push(entry);
17    let i = heap.length - 1;
18    while (i > 0) {
19      const p = Math.floor((i - 1) / 2);
20      if (heap[p][0] <= heap[i][0]) break;
21      [heap[p], heap[i]] = [heap[i], heap[p]];
22      i = p;
23    }
24  };
25 
26  const heapPop = (): [number, number] => {
27    const top = heap[0];
28    const last = heap.pop()!;
29    if (heap.length > 0) {
30      heap[0] = last;
31      let i = 0;
32      while (true) {
33        let s = i;
34        const l = 2 * i + 1, r = 2 * i + 2;
35        if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
36        if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
37        if (s === i) break;
38        [heap[s], heap[i]] = [heap[i], heap[s]];
39        i = s;
40      }
41    }
42    return top;
43  };
44 
45  for (const [q, origIdx] of indexedQueries) {
46    // Add every interval whose start <= q (it could cover q)
47    while (ivIdx < intervals.length && intervals[ivIdx][0] <= q) {
48      const [start, end] = intervals[ivIdx];
49      heapPush([end - start + 1, end]);   // key = size, payload = end
50      ivIdx++;
51    }
52 
53    // Evict intervals that ended before q (they can't cover q)
54    while (heap.length > 0 && heap[0][1] < q) {
55      heapPop();
56    }
57 
58    // Heap top = smallest still-valid interval covering q
59    if (heap.length > 0) {
60      result[origIdx] = heap[0][0];
61    }
62  }
63 
64  return result;
65}
queries (sorted)2i=03i=14i=25i=3
State
[1,4] [2,4] [3,6] [4,4]
sortedIntervals
[]
heap
0
heap size
0
ivIdx
[?, ?, ?, ?]
result
current queryinterval pushed to heapexpired (evicted from heap)answer recorded
slowfast

TYPESCRIPT The solution, annotated

minInterval.ts
function minInterval(intervals: number[][], queries: number[]): number[] {
  // Sort intervals by start value so we can add them lazily as queries grow
  intervals.sort((a, b) => a[0] - b[0]);

  // Process queries in ascending order, then restore original positions
  const indexedQueries = queries.map((q, i) => [q, i] as [number, number]);
  indexedQueries.sort((a, b) => a[0] - b[0]);

  const result: number[] = new Array(queries.length).fill(-1);

  // Min-heap keyed by interval size: [size, end]
  const heap: [number, number][] = [];
  let ivIdx = 0;

  const heapPush = (entry: [number, number]) => {
    heap.push(entry);
    let i = heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[p][0] <= heap[i][0]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  };

  const heapPop = (): [number, number] => {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      while (true) {
        let s = i;
        const l = 2 * i + 1, r = 2 * i + 2;
        if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
        if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
        if (s === i) break;
        [heap[s], heap[i]] = [heap[i], heap[s]];
        i = s;
      }
    }
    return top;
  };

  for (const [q, origIdx] of indexedQueries) {
    // Add every interval whose start <= q (it could cover q)
    while (ivIdx < intervals.length && intervals[ivIdx][0] <= q) {
      const [start, end] = intervals[ivIdx];
      heapPush([end - start + 1, end]);   // key = size, payload = end
      ivIdx++;
    }

    // Evict intervals that ended before q (they can't cover q)
    while (heap.length > 0 && heap[0][1] < q) {
      heapPop();
    }

    // Heap top = smallest still-valid interval covering q
    if (heap.length > 0) {
      result[origIdx] = heap[0][0];
    }
  }

  return result;
}

Reading it block by block

Line 3 — sort intervals by start. After sorting, a single pointer ivIdx can sweep forward as queries increase — no need to revisit earlier intervals.
Lines 6–7 — offline query setup. Wrap each query with its original index so answers land in the right position. Sorting queries is the key move: it lets the interval pointer advance monotonically.
Lines 15–34 — inline min-heap helpers. JavaScript has no built-in priority queue; these 20-line helpers provide heapPush and heapPopordered by the first tuple element (size). In an interview you can name "min-heap keyed by size" and code just the usage.
Lines 38–42 — push phase. While the next sorted interval starts ≤ current query, push [size, end]. This is O(log n) per push and happens at most n times total.
Lines 45–47 — evict phase.Pop while the heap top's end is < current query. That interval is expired — it ended before q, so it can't contain it. Amortised O(1): each entry evicted at most once across all queries.
Lines 50–52 — read answer. The heap top is now the smallest interval that (a) starts ≤ q and (b) ends ≥ q. Its heap[0][0] is the size. Store it at the original query index.
Complexity → O((n + q) log n) time: sorting intervals is O(n log n), sorting queries is O(q log q), and each interval is pushed and popped from the heap at most once for a total of O(n log n) heap operations across all queries. Space: O(n) heap + O(q) output.

INTERVIEWFollow-ups they'll ask

  • "What if queries arrive online (not all at once)?" You lose the offline sort trick. A segment tree or interval tree answers point-stabbing queries in O(log n) each; a sorted list + binary search gives the candidates but you still need to filter by end.
  • "Return the actual interval, not just the size?" Store [size, end, start] in the heap — the start is recoverable as end - size + 1.
  • "What if you want the k smallest intervals per query?" Keep popping the heap up to k times, recording the tops, then re-push them (or use a different data structure). O(k log n) per query.
  • "What's the brute-force and why is this faster?" For each query, scan all n intervals and filter those that contain it — O(n · q). Sorting and the heap reduce it to O((n + q) log n) by avoiding repeated scans.
  • "What if interval starts/ends can be negative?" No change — the sort comparator and heap ordering work for all integers.

OPTIMAL Sorting

minInterval.ts
function minInterval(intervals: number[][], queries: number[]): number[] {
  // Sort intervals by start value so we can add them lazily as queries grow
  intervals.sort((a, b) => a[0] - b[0]);

  // Process queries in ascending order, then restore original positions
  const indexedQueries = queries.map((q, i) => [q, i] as [number, number]);
  indexedQueries.sort((a, b) => a[0] - b[0]);

  const result: number[] = new Array(queries.length).fill(-1);

  // Min-heap keyed by interval size: [size, end]
  const heap: [number, number][] = [];
  let ivIdx = 0;

  const heapPush = (entry: [number, number]) => {
    heap.push(entry);
    let i = heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[p][0] <= heap[i][0]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  };

  const heapPop = (): [number, number] => {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      while (true) {
        let s = i;
        const l = 2 * i + 1, r = 2 * i + 2;
        if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
        if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
        if (s === i) break;
        [heap[s], heap[i]] = [heap[i], heap[s]];
        i = s;
      }
    }
    return top;
  };

  for (const [q, origIdx] of indexedQueries) {
    // Add every interval whose start <= q (it could cover q)
    while (ivIdx < intervals.length && intervals[ivIdx][0] <= q) {
      const [start, end] = intervals[ivIdx];
      heapPush([end - start + 1, end]);   // key = size, payload = end
      ivIdx++;
    }

    // Evict intervals that ended before q (they can't cover q)
    while (heap.length > 0 && heap[0][1] < q) {
      heapPop();
    }

    // Heap top = smallest still-valid interval covering q
    if (heap.length > 0) {
      result[origIdx] = heap[0][0];
    }
  }

  return result;
}
Complexity → O((n + q) log n) time: sorting intervals is O(n log n), sorting queries is O(q log q), and each interval is pushed and popped from the heap at most once for a total of O(n log n) heap operations across all queries. Space: O(n) heap + O(q) output.

ALT 1 Brute force — scan every interval per query

O(q · n) time · O(1) extra space (besides output)

The obvious-but-slow baseline: for each query, walk every interval and keep the smallest covering size — no sorting, no heap, just the definition spelled out. It is the version the offline sort + min-heap exists to speed up.

approach-2.ts
function minInterval(intervals: number[][], queries: number[]): number[] {
  const result: number[] = new Array(queries.length).fill(-1);

  for (let qi = 0; qi < queries.length; qi++) {
    const q = queries[qi];
    let best = -1; // smallest covering size seen so far; -1 = none yet

    // Scan every interval; an interval [start, end] covers q iff start <= q <= end
    for (let ii = 0; ii < intervals.length; ii++) {
      const start = intervals[ii][0];
      const end = intervals[ii][1];
      if (start <= q && q <= end) {
        const size = end - start + 1;
        if (best === -1 || size < best) {
          best = size;
        }
      }
    }

    result[qi] = best; // stays -1 if no interval covered q
  }

  return result;
}
Note → Correct and trivial to reason about, but it re-scans all n intervals for every one of the q queries. When both q and n are large (each up to ~105), the ~1010 operations TLE — which is exactly what motivates sorting the queries and sweeping with a self-evicting min-heap.

MNEMONIC The one-liner

"Sort both. For each query: push starts ≤ q, pop ends < q, read the top."

TRIGGERS When you see ___ → reach for ___

"smallest interval containing each query point"offline sort + min-heap by size
point queries against a set of intervalssort queries + sweep interval pointer
need to evict stale heap entries lazilypop while heap[0].end < query
"offline queries" — all queries known upfrontsort queries, restore original indices

SKELETON The reusable shape

skeleton.ts
// Sort intervals by start; sort queries (keep original index)
intervals.sort((a, b) => a[0] - b[0]);
const qs = queries.map((q, i) => [q, i]).sort((a, b) => a[0] - b[0]);
const ans = new Array(queries.length).fill(-1);
// min-heap keyed by size: [size, end]
const heap: [number, number][] = [];
let iv = 0;

for (const [q, idx] of qs) {
  while (iv < intervals.length && intervals[iv][0] <= q) {
    heapPush([intervals[iv][1] - intervals[iv][0] + 1, intervals[iv][1]]);
    iv++;
  }
  while (heap.length && heap[0][1] < q) heapPop();   // expired
  if (heap.length) ans[idx] = heap[0][0];
}
return ans;

FLASHCARDS Tap to flip

Why sort the queries before processing them?
So the interval pointer can advance forward only — each interval is pushed at most once. Sorting queries makes the interval sweep monotonic.
tap to flip
1 / 8
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
What is the time complexity of the sort + offline min-heap approach?
QUESTION 02
You push entries into the min-heap as [size, end]. What would go wrong if you keyed by end instead of size?
QUESTION 03
Trace the worked example: intervals = [[1,4],[2,4],[3,6],[4,4]], query q = 4. Which intervals are in the heap just before reading the answer for q=4 (after eviction)?
QUESTION 04
Why do you sort queries ascending (offline) rather than processing them in original order?
QUESTION 05
When should you evict an entry from the heap?
QUESTION 06
What does the heap top represent at the moment you read the answer for query q?
QUESTION 07
intervals = [[2,3],[2,5],[1,8]], queries = [2,5,6]. What is the answer for query 5?
QUESTION 08
#1851 · Minimum Interval to Include Each QuerySort intervals and process queries offline in sorted order. A min-heap keyed by interval size carries live intervals; for each query, add all intervals starting ≤ query, evict those ending < query, and the heap top is the smallest covering interval.Which algorithmic approach does this primarily use?
QUESTION 09
#1851 · Minimum Interval to Include Each QuerySort intervals and process queries offline in sorted order. A min-heap keyed by interval size carries live intervals; for each query, add all intervals starting ≤ query, evict those ending < query, and the heap top is the smallest covering interval.Which implementation correctly solves it?