LeetCode 1851 · Hard · Intervals

Minimum Interval to Include Each Query

For each query point q, find the shortest interval [l, r] with l ≤ q ≤ r and report its size r − l + 1, or -1 if no interval contains q.

O(n log n + m log m)time
O(n + m)space
sorted sweepmin-heap of {size, r}

intervals: 1–8, 1 ≤ l ≤ r ≤ 25 · queries: 1–6 integers from 1 to 25

Number line intervals sorted by l · yellow: in the heap · dashed: popped · dots: queries

minHeap {size, r} · tree shows size · smallest size at the root

minHeap list size in the box, r below

public int[] minInterval(int[][] intervals, int[] queries) { Comparator<int[]> cmp = (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]; Arrays.sort(intervals, cmp); PriorityQueue<int[]> minHeap = new PriorityQueue<>(cmp); Map<Integer, Integer> res = new HashMap<>(); int i = 0; int[] sortedQ = queries.clone(); Arrays.sort(sortedQ); for (int q : sortedQ) { while (i < intervals.length && intervals[i][0] <= q) { int l = intervals[i][0]; int r = intervals[i][1]; minHeap.offer(new int[]{r - l + 1, r}); i++; } while (!minHeap.isEmpty() && minHeap.peek()[1] < q) { // ended minHeap.poll(); } res.put(q, minHeap.isEmpty() ? -1 : minHeap.peek()[0]); } int[] ans = new int[queries.length]; for (int j = 0; j < queries.length; j++) { ans[j] = res.get(queries[j]); } return ans;}
q
—
i
0
minHeap
[]
res
{}

Why it works

  1. Brute force scans every interval for every query: O(n · m). Too slow at 10⁵ each.
  2. Answer the queries in sorted order. As q grows, an interval whose l ≤ q becomes a candidate once and stays one until q passes its r. So intervals enter the heap once, in order of l, and leave once.
  3. The heap is keyed by size, with r riding along. The root is the shortest candidate. If it already ended (r < q) it is useless for this and every later query, so pop it. Expired intervals deeper in the heap can wait: they only matter if they reach the root.
  4. Cost: sorting is O(n log n + m log m); each interval is pushed and popped at most once, O(n log n). The heap and the answers take O(n + m).
  5. Pitfall: the answers must come back in the original query order, and duplicates must share an answer. That is why res is a HashMap keyed by q, read back in the order of queries. Sort a clone of queries, not the array itself, or the original order is lost.