363. Minimum Interval to Include Each Query

Process queries in increasing order. Add every interval that has started (left <= query) into a min-heap keyed by size, and lazily discard intervals that have already ended (right < query). The heap top is then the smallest covering interval.

Offline, sorted queries

Answer queries in increasing order so intervals are only ever added, never removed early.

1. Sort intervals by left and queries ascending (remember original positions).
2. For each query q:
   • Push every interval with left <= q into a min-heap keyed by (size, right).
   • Pop intervals whose right < q (they can't cover q).
   • The heap top (if any) is the smallest interval covering q; otherwise -1.

Each interval is pushed and popped at most once.

Worked example

intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5] → [3,3,1,4] (e.g. query 4 is covered by [4,4] of size 1).

Complexity

• Time: O((n + q) log n).
• Space: O(n).

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        Integer[] order = new Integer[queries.length];
        for (int i = 0; i < queries.length; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> Integer.compare(queries[a], queries[b]));

        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); // (size, right)
        int[] res = new int[queries.length];
        int i = 0;
        for (int qi : order) {
            int q = queries[qi];
            while (i < intervals.length && intervals[i][0] <= q) {
                heap.offer(new int[]{intervals[i][1] - intervals[i][0] + 1, intervals[i][1]});
                i++;
            }
            while (!heap.isEmpty() && heap.peek()[1] < q) {
                heap.poll();
            }
            res[qi] = heap.isEmpty() ? -1 : heap.peek()[0];
        }
        return res;
    }
}