Minimum Interval to Include Each Query
You are given closed intervals intervals[i] = [left, right]right - left + 1queries[j]left <= queries[j] <= right
Limits: 1 <= intervals.length <= 105, 1 <= queries.length <= 105, 1 <= left <= right <= 107, and 1 <= queries[j] <= 107.
Example 1
Output: [3,3,1,4]
Explanation: 2 and 3 fit best in [2,4] (size 3), 4 in [4,4] (size 1), and 5 only in [3,6] (size 4).
Example 2
Output: [2,-1,4,6]
Explanation: no interval contains 19.
How to Think About It
Step 1: The brute force
For each query, scan every interval, keep the ones that contain it, and take the smallest size. That is O(n × q) checks, up to 1010 at the limits, far too slow.
Step 2: Answer the queries from left to right
The order of the answers is fixed, but the order in which we compute them is up to us. Sort the query positions by value and sweep a point from small to large, writing each answer back to its original slot.
Step 3: Intervals switch on at their left end
Sort the intervals by leftleft <= q
Step 4: Keep the pool in a min-heap by size
We want the smallest interval in the pool that still covers q. A min-heap ordered by size gives the smallest one on top in O(log n) per change.
Step 5: Throw away intervals that ended, but only from the top
An interval on top with right < q
Ended intervals that are not on top may stay in the heap. That is harmless: they are larger than the top, so they cannot be the answer now, and they get popped later if they ever rise to the top. Sorting by start and keeping a min-heap of what has begun is also the core of
Walkthrough
Example 2. Sorted by left, the intervals are [1,8], [2,3], [2,5], [20,25]. Heap entries are written as (size, right).
| Query (original index) | Intervals added | Popped as ended | Heap after | Answer |
|---|---|---|---|---|
| 2 (0) | [1,8], [2,3], [2,5] | none | (2,3), (4,5), (8,8) | 2 |
| 5 (2) | none | (2,3) | (4,5), (8,8) | 4 |
| 19 (1) | none | (4,5), (8,8) | empty | -1 |
| 22 (3) | [20,25] | none | (6,25) | 6 |
Writing each answer at its original index gives [2, -1, 4, 6].
Java Solution
The method sweeps the queries in increasing order, adds every interval that has started to a min-heap by size, and drops ended intervals from the top before reading the answer.
- Sorting indices, not values:
holds query indices sorted by their values. The answer fororder then goes toqueries[idx] , which keeps the original order.answer[idx] - One pointer for intervals:
only moves forward, so all intervals are added once in total, not once per query.next - The size: both ends count, so
has size 1 and the answer for query 4 in Example 1 is 1. The largest possible size is 107, which fits easily in an[4,4] .int - Equal queries: a repeated query finds nothing new to add or pop and gets the same answer. With
and queries[[1,3]] the result is[2,2,4] .[3,3,-1]
A common mistake is to sort a copy of queries[2,4,-1,6][2,-1,4,6]
import java.util.Arrays;
import java.util.PriorityQueue;
public class MinimumIntervalToIncludeEachQuery {
public int[] minInterval(int[][] intervals, int[] queries) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
Integer[] order = new Integer[queries.length]; // query indices, smallest query first
for (int i = 0; i < order.length; i++) order[i] = i;
Arrays.sort(order, (a, b) -> Integer.compare(queries[a], queries[b]));
// {size, right end}: the smallest interval that has started is on top
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
int[] answer = new int[queries.length];
int next = 0; // first interval not yet added
for (int idx : order) {
int q = queries[idx];
while (next < intervals.length && intervals[next][0] <= q) {
int[] in = intervals[next++];
heap.add(new int[]{in[1] - in[0] + 1, in[1]});
}
while (!heap.isEmpty() && heap.peek()[1] < q) {
heap.poll(); // ended before q, so it also misses every later query
}
answer[idx] = heap.isEmpty() ? -1 : heap.peek()[0]; // write to the original position
}
return answer;
}
}
Complexity
- Time: O(n log n + q log q), where n is the number of intervals and q the number of queries. The two sorts cost n log n and q log q. Each interval is pushed once and popped at most once, and each heap operation costs O(log n).
- Space: O(n + q). The heap can hold every interval at once, as when all of them start before the first query. The
andorder arrays add one slot per query.answer
On 105 random intervals and queries at the full limits, the method finishes in well under a second. For a simpler first problem on sorted intervals, see