Minimum Interval to Include Each Query

Examples

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

For query 4, intervals [1,4] (size 4), [2,4] (size 3), [3,6] (size 4), and [4,4] (size 1) all contain it — the smallest is [4,4], size 1.

Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
Output: [2,-1,4,6]

No interval contains 19, so that answer is -1. Query 22 is only inside [20,25], size 6.

Constraints

• 1 <= intervals.length <= 10^5

• 1 <= queries.length <= 10^5

• intervals[i].length == 2

• 1 <= start <= end <= 10^7

• 1 <= query <= 10^7

Approach

The straightforward approach checks, for every single query, every interval to see if it contains that point and keeps the smallest one that does. That works but redoes a full scan for every query.

The faster approach processes queries in sorted order (remembering their original positions so the answers can be placed back correctly) alongside intervals sorted by start time. As the query value increases, sweep forward through the intervals: any interval whose start is at or before the current query becomes "available" and goes into a min-heap ordered by size. Before answering each query, pop off any available interval whose end is already behind the current query — it's expired and can never help this or any later query. Whatever remains at the top of the heap is the smallest interval currently containing the query — exactly the answer needed.

Solutions

Brute Force — Check Every Interval per Query

For each query, scan every interval. If the interval contains the query point, compute its size and keep track of the smallest one seen. If nothing contains the query, its answer is -1.

function minInterval(intervals, queries) {
  const result = [];

  for (const q of queries) {
    let best = -1;
    for (const [l, r] of intervals) {
      if (l <= q && q <= r) {
        const size = r - l + 1;
        if (best === -1 || size < best) {
          best = size;
        }
      }
    }
    result.push(best);
  }

  return result;
}

Time: O(n * q) — every query scans every interval · Space: O(1) extra space, besides the output array

Optimal — Sort + Min-Heap Sweep

Sort the intervals by start time, and sort the queries by value while remembering each query's original index (so the final answers can be placed back in the right slots).

Sweep through the sorted queries. For each one: first, push every interval whose start is at or before this query into a min-heap keyed by interval size (breaking ties doesn't matter, but the end is stored too so expired entries can be recognized). Then, pop off any interval at the top of the heap whose end has already fallen behind the current query — it's no longer relevant to this or any future (larger) query. Whatever's left on top of the heap, if anything, is the smallest interval still covering this query.

function minInterval(intervals, queries) {
  const sortedIntervals = [...intervals].sort((a, b) => a[0] - b[0]);
  const sortedQueries = queries
    .map((q, index) => [q, index])
    .sort((a, b) => a[0] - b[0]);

  const answer = new Array(queries.length).fill(-1);
  const heap = []; // entries: [size, end]
  let i = 0;

  const heapPush = (item) => {
    heap.push(item);
    let idx = heap.length - 1;
    while (idx > 0) {
      const parent = (idx - 1) >> 1;
      if (heap[parent][0] <= heap[idx][0]) break;
      [heap[parent], heap[idx]] = [heap[idx], heap[parent]];
      idx = parent;
    }
  };

  const heapPop = () => {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length > 0) {
      heap[0] = last;
      let idx = 0;
      while (true) {
        const left = idx * 2 + 1;
        const right = idx * 2 + 2;
        let smallest = idx;
        if (left < heap.length && heap[left][0] < heap[smallest][0]) smallest = left;
        if (right < heap.length && heap[right][0] < heap[smallest][0]) smallest = right;
        if (smallest === idx) break;
        [heap[smallest], heap[idx]] = [heap[idx], heap[smallest]];
        idx = smallest;
      }
    }
    return top;
  };

  for (const [q, originalIndex] of sortedQueries) {
    while (i < sortedIntervals.length && sortedIntervals[i][0] <= q) {
      const [l, r] = sortedIntervals[i];
      heapPush([r - l + 1, r]);
      i++;
    }

    while (heap.length > 0 && heap[0][1] < q) {
      heapPop();
    }

    if (heap.length > 0) {
      answer[originalIndex] = heap[0][0];
    }
  }

  return answer;
}

Time: O((n + q) log n) — sorting plus heap operations for each interval and query · Space: O(n + q) for the heap, sorted queries, and answer array