Minimum Interval to Include Each Query

The problem

Each interval in intervals is written [left, right] and contains every number from left to right, both ends included. Its length is right - left + 1, so [2, 4] has length 3 and [4, 4] has length 1. For each number in queries, find the shortest interval that contains it. Return a list with that interval's length for each query, or -1 where no interval contains the query, in the same order as queries. Intervals may overlap or repeat and come in no particular order, a query may repeat, and intervals may be empty.

What to write

function solve(intervals: number[][], queries: number[]): number[]

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

Output
[3,3,1,4]

Input
intervals = [[2,3],[2,5],[1,8],[20,25]]
queries = [2,19,5,22]

Output
[2,-1,4,6]

Constraints

Return answers in original query order.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Both ends of an interval count, so [4, 4] contains the query 4 and has length 1. The answers must come back in the order the queries were given, but nothing forces you to work them out in that order.

2. Hint 2: Ask a smaller question

   Take the intervals [2, 3], [2, 5], [1, 8] and the queries 2, 5 and 19, in that order. Which intervals contain 2? Which of those still matter for 5? Can an interval that ends before 5 ever help with 19?

3. Hint 3: Name the pattern

   Answer the queries from smallest to largest. As the query grows, an interval comes into play when it starts and is useless for good once it has ended, and you always want the shortest one in play. A min-heap, a container that keeps its smallest item on top, hands that out. This is a heap as a priority queue. Read the lesson on heap as a priority queue.

4. Hint 4: State the invariant

   When a query is answered, the heap has received every interval that starts at or before it, and the top interval, if there is one, ends at or after it. So the top contains the query, and no interval that was removed or is still waiting does.

5. Hint 5: Sketch the pseudocode

   Sort the intervals by start. Sort the queries, keeping positions. Use a min-heap by length; answers start at -1. For each query q: push (length, right end) of every interval not yet pushed that starts at or before q. Pop while the top's right end is below q. If a top remains, write its length at q's position.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Process queries in sorted order, adding intervals when they start. A min-heap by length supplies the smallest interval after expired entries are removed.

The slow way

For each query, look at every interval, keep the ones that contain the query, and take the smallest length among them, or -1 if there is none. It is correct, but every query walks the whole list: n intervals and q queries cost n × q steps.

The insight

The answers must be returned in the given order, but they can be worked out in any order. Take the queries from smallest to largest, and the intervals that might contain the query change in a simple way: an interval joins when the query reaches its start, and it is useless forever once the query has passed its end.

Step by step

1. Sort the intervals by start, and the queries with their positions. Both lists are then walked from left to right together. Each query is paired with its position in queries, because the answers must come back in the original order.
2. Prepare a min-heap ordered by length and an answer list of -1. A min-heap is a container that always has its smallest item on top, here the shortest interval, stored with its right end. Every answer starts as -1 and keeps it if no interval contains the query.
3. Take the queries from the smallest to the largest. In this order, an interval that starts at or before one query also starts at or before every later query. So no interval has to be pushed twice, and the position in the interval list never moves back.
4. Push every interval that starts at or before the query. Only an interval that has started can contain the query. The intervals are sorted by start, so one position that only moves forward finds them, and each interval is pushed at most once for all the queries together.
5. Pop the top interval while it ends before the query. An interval that ends before this query cannot contain it, or any later query, because the queries only grow. So that interval can go for good. Ended intervals deeper in the heap are harmless until they reach the top.
6. The top is now the shortest interval containing the query: record it. Everything in the heap starts at or before the query, and the top also ends at or after the query, so the top contains it. The heap is ordered by length, so nothing shorter does. An empty heap leaves -1.
7. Return the answers, each at its query's original position. Each answer was written at the position its query had in the input, not at its place in the sorted order. So the list lines up with queries as given.

The same numbered steps are the comments in each solution.

function solve(intervals, queries) {
  // 1. Sort the intervals by start, and the queries with their positions
  intervals.sort((a, b) => a[0] - b[0]);
  const sorted = queries.map((q, i) => [q, i]).sort((a, b) => a[0] - b[0]);
  // 2. Prepare a min-heap ordered by length and an answer list of -1
  const heap = [],
    out = Array(queries.length).fill(-1);
  // JavaScript has no built-in heap, so push and pop are written by hand.
  // The heap is an array of [length, right end] pairs. The pair at index i has
  // its parent at index (i - 1) >>> 1, which is (i - 1) / 2 rounded down. No
  // pair is shorter than its parent, so the shortest is always at index 0.
  // push adds a pair at the end and moves it up while its parent is longer.
  function push(v) {
    heap.push(v);
    let i = heap.length - 1;
    while (i) {
      const p = (i - 1) >>> 1;
      if (heap[p][0] <= heap[i][0]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  }
  // pop removes the pair at index 0. The last pair takes its place and moves
  // down, each time swapping with its shorter child, while that child is shorter.
  function pop() {
    const last = heap.pop();
    if (!heap.length) return;
    heap[0] = last;
    let i = 0;
    while (true) {
      let c = 2 * i + 1;
      if (c >= heap.length) break;
      if (c + 1 < heap.length && heap[c + 1][0] < heap[c][0]) c++;
      if (heap[i][0] <= heap[c][0]) break;
      [heap[i], heap[c]] = [heap[c], heap[i]];
      i = c;
    }
  }
  // 3. Take the queries from the smallest to the largest
  let j = 0;
  for (const [q, i] of sorted) {
    // 4. Push every interval that starts at or before the query
    while (j < intervals.length && intervals[j][0] <= q) {
      const [l, r] = intervals[j++];
      push([r - l + 1, r]);
    }
    // 5. Pop the top interval while it ends before the query
    while (heap.length && heap[0][1] < q) pop();
    // 6. The top is now the shortest interval containing the query: record it
    if (heap.length) out[i] = heap[0][0];
  }
  // 7. Return the answers, each at its query's original position
  return out;
}

function solve(intervals: number[][], queries: number[]): number[] {
  // 1. Sort the intervals by start, and the queries with their positions
  intervals.sort((a, b) => a[0] - b[0]);
  const sorted = queries.map((q, i) => [q, i]).sort((a, b) => a[0] - b[0]);
  // 2. Prepare a min-heap ordered by length and an answer list of -1
  const heap: number[][] = [],
    out = Array(queries.length).fill(-1);
  // JavaScript has no built-in heap, so push and pop are written by hand.
  // The heap is an array of [length, right end] pairs. The pair at index i has
  // its parent at index (i - 1) >>> 1, which is (i - 1) / 2 rounded down. No
  // pair is shorter than its parent, so the shortest is always at index 0.
  // push adds a pair at the end and moves it up while its parent is longer.
  function push(v: number[]): void {
    heap.push(v);
    let i = heap.length - 1;
    while (i) {
      const p = (i - 1) >>> 1;
      if (heap[p][0] <= heap[i][0]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  }
  // pop removes the pair at index 0. The last pair takes its place and moves
  // down, each time swapping with its shorter child, while that child is shorter.
  function pop(): void {
    const last = heap.pop()!;
    if (!heap.length) return;
    heap[0] = last;
    let i = 0;
    while (true) {
      let c = 2 * i + 1;
      if (c >= heap.length) break;
      if (c + 1 < heap.length && heap[c + 1][0] < heap[c][0]) c++;
      if (heap[i][0] <= heap[c][0]) break;
      [heap[i], heap[c]] = [heap[c], heap[i]];
      i = c;
    }
  }
  // 3. Take the queries from the smallest to the largest
  let j = 0;
  for (const [q, i] of sorted) {
    // 4. Push every interval that starts at or before the query
    while (j < intervals.length && intervals[j][0] <= q) {
      const [l, r] = intervals[j++];
      push([r - l + 1, r]);
    }
    // 5. Pop the top interval while it ends before the query
    while (heap.length && heap[0][1] < q) pop();
    // 6. The top is now the shortest interval containing the query: record it
    if (heap.length) out[i] = heap[0][0];
  }
  // 7. Return the answers, each at its query's original position
  return out;
}

import heapq


def solve(intervals, queries):
    # 1. Sort the intervals by start, and the queries with their positions
    intervals = sorted(intervals, key=lambda interval: interval[0])
    sorted_queries = sorted((query, i) for i, query in enumerate(queries))
    # 2. Prepare a min-heap ordered by length and an answer list of -1
    # heapq keeps the smallest pair at heap[0]. A pair is (length, right end),
    # and pairs are compared by length first, then by right end.
    heap = []
    out = [-1] * len(queries)
    # 3. Take the queries from the smallest to the largest
    j = 0
    for query, i in sorted_queries:
        # 4. Push every interval that starts at or before the query
        while j < len(intervals) and intervals[j][0] <= query:
            left, right = intervals[j]
            heapq.heappush(heap, (right - left + 1, right))
            j += 1
        # 5. Pop the top interval while it ends before the query
        while heap and heap[0][1] < query:
            heapq.heappop(heap)
        # 6. The top is now the shortest interval containing the query: record it
        if heap:
            out[i] = heap[0][0]
    # 7. Return the answers, each at its query's original position
    return out

Example 2, traced

Input
intervals = [[2,3],[2,5],[1,8],[20,25]]
queries = [2,19,5,22]

Output
[2,-1,4,6]

Why it works

When a query is answered, every interval that starts at or before it has been pushed, and the only ones removed ended before this query or an earlier one. So every interval that contains the query is in the heap. After the pops, the top ends at or after the query, so the top contains the query, and no interval in the heap is shorter.

Time and space

Time O((n + q) log(n + q)), extra space O(n + q). Sorting costs about n log n steps for n intervals and q log q for q queries. Each interval is pushed and popped at most once, about log n steps each: O((n + q) log(n + q)) time. The heap, sorted queries and answers take O(n + q) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Pop in a loop, not once. Several intervals can have ended since the last query. With a single pop, query 19 in example 2 removes [2, 5], finds [1, 8] on top, and answers 8 instead of -1.
• Write each answer at the query's original position. Written in sorted order, example 2 returns [2, 4, -1, 6] instead of [2, -1, 4, 6]: the answers for 5 and 19 change places.
• Order the heap by length, not by right end. With [5, 10] and [7, 11] and the query 7, the earliest end puts [5, 10] on top and answers 6. The right answer is 5, from [7, 11].

Pattern

Heap as a priority queue. Builds on Last Stone Weight and Meeting Rooms II.

Keep going