1851. Minimum Interval to Include Each Query

Given intervals [left, right] (inclusive, size = right − left + 1) and a list of queries, return for each query the size of the smallest interval that contains it, or -1 if none does.

Sort intervals by start and answer queries in increasing order. Push every interval that has started into a min-heap keyed by size, pop the ones that already ended, and the heap top is the answer.

1function minInterval(intervals: number[][], queries: number[]): number[] {
2  intervals.sort((a, b) => a[0] - b[0]);
3  const order = queries.map((_, i) => i).sort((a, b) => queries[a] - queries[b]);
4  const heap = new MinPriorityQueue<[number, number]>((e) => e[0]); // [size, right]
5  const res = new Array(queries.length).fill(-1);
6  let i = 0;
7  for (const qi of order) {
8    const q = queries[qi];
9    while (i < intervals.length && intervals[i][0] <= q) {
10      const [l, r] = intervals[i++]; heap.enqueue([r - l + 1, r]);
11    }
12    while (heap.size() && heap.front()![1] < q) heap.dequeue();
13    if (heap.size()) res[qi] = heap.front()![0];
14  }
15  return res;
16}

intervals (sorted by start)

[1,4]

[2,4]

[3,6]

[4,4]

min-heap (size, right)

empty

answers

Sort intervals by start; process queries from smallest to largest.

1 / 0

Space: play/pause · ←/→: step