Minimum Interval to Include Each Query
Problem
intervals[i] = [left, right], whose size is
right - left + 1, and an array queries. For each query
q, report the size of the smallest interval with
left ≤ q ≤ right, or -1 if none contains it. Answers
must be returned in the original query order.intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]Output[3,3,1,4]intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]Output[2,-1,4,6]1 ≤ intervals.length, queries.length ≤ 105 · 1 ≤ left ≤ right ≤ 107 · 1 ≤ queries[j] ≤ 107
Try it yourself
class Solution {
public int[] minInterval(int[][] intervals, int[] queries) {
}
}
Instinct See [start, end] pairs, meetings, bookings or the word "overlap"? Sort by an endpoint, then sweep left to right carrying one running fact.
Memory hack Sort, then sweep - start time to merge, end time to choose, +1/-1 events to count the crowd.
Open the Intervals & Line Sweep guide →Approaches
Brute ForceScan All Intervals per Query
O(n·q)Space O(1) extraFor each query, look at every interval, keep those that contain the query and remember the smallest size. Straightforward, but with 105 of each it is 1010 checks.
public int[] minInterval(int[][] intervals, int[] queries) { int[] ans = new int[queries.length]; for (int j = 0; j < queries.length; j++) { int q = queries[j], best = Integer.MAX_VALUE; for (int[] iv : intervals) { if (iv[0] <= q && q <= iv[1]) best = Math.min(best, iv[1] - iv[0] + 1); } ans[j] = best == Integer.MAX_VALUE ? -1 : best; } return ans; }
Perfect as a correctness reference; far too slow at full scale.
OptimalSorted Queries + Min-Heap by Size
O(n log n + q log q)Space O(n + q)Sort intervals by left end and query indices by value. For each query in
ascending order, push every interval whose left ≤ q as
(size, right), then pop heap tops whose right < q — they
can't contain this or any later query. The top left is the smallest interval
containing q.
public int[] minInterval(int[][] intervals, int[] queries) { int[][] iv = intervals.clone(); Arrays.sort(iv, (a, b) -> Integer.compare(a[0], b[0])); Integer[] order = new Integer[queries.length]; for (int j = 0; j < order.length; j++) order[j] = j; Arrays.sort(order, (a, b) -> Integer.compare(queries[a], queries[b])); // {size, right}: smallest size on top PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); int[] ans = new int[queries.length]; int i = 0; for (int idx : order) { int q = queries[idx]; while (i < iv.length && iv[i][0] <= q) { // intervals that have started heap.offer(new int[]{iv[i][1] - iv[i][0] + 1, iv[i][1]}); i++; } while (!heap.isEmpty() && heap.peek()[1] < q) heap.poll(); // already ended ans[idx] = heap.isEmpty() ? -1 : heap.peek()[0]; } return ans; }
Every interval is pushed and popped at most once; sorting dominates.
q also ends
before every later (larger) query, so it can be discarded only when it surfaces.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Scan All Intervals per Query | O(n·q) | O(1) extra |
| Optimal | Sorted Queries + Min-Heap by Size | O(n log n + q log q) | O(n + q) |
- Answering in sorted order and forgetting to write results back to original indices.
- Computing size as
right - left— the interval is closed, add 1. - Removing expired intervals eagerly from the middle of the heap — lazy popping suffices.
- Say “offline” early: sorting queries is allowed because all are known upfront.
- Justify why an interval that expired for one query never helps a later one.
- Mention the alternative: sort intervals by size and fill queries with a union-find.