Minimum Interval to Include Each Query

You are given closed intervals intervals[i] = [left, right]. The size of an interval is the count of integers in it, right - left + 1. For each queries[j], return the size of the smallest interval with left <= queries[j] <= right, or -1 if there is none. Answers go in the same order as the queries. This is LeetCode 1851.

Limits: 1 <= intervals.length <= 105, 1 <= queries.length <= 105, 1 <= left <= right <= 107, and 1 <= queries[j] <= 107.

Example 1
Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
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
Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
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 left. When the sweep reaches query q, every interval with left <= q has started. Add those to a pool with a single pointer, so each interval enters the pool exactly once over the whole sweep.

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 does not cover q. Queries only grow, so it will never cover a later query either, and it can be popped for good. Pop until the top covers q, and its size is the answer.

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 Meeting Rooms II, where the heap is ordered by end time instead of size.

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 addedPopped as endedHeap afterAnswer
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: order holds query indices sorted by their values. The answer for queries[idx] then goes to answer[idx], which keeps the original order.
  • One pointer for intervals: next only moves forward, so all intervals are added once in total, not once per query.
  • The size: both ends count, so [4,4] 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 int.
  • Equal queries: a repeated query finds nothing new to add or pop and gets the same answer. With [[1,3]] and queries [2,2,4] the result is [3,3,-1].

A common mistake is to sort a copy of queries and store answers in sorted order. The values are right but in the wrong slots: Example 2 returns [2,4,-1,6] instead of [2,-1,4,6].

Java
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 order and answer arrays add one slot per query.

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 Merge Intervals.