Minimum Interval to Include Each Query

NeetCode: Minimum Interval to Include Each Query · LeetCode: 1851. Minimum Interval to Include Each Query · Difficulty: Hard

You are given intervals [left, right] (inclusive; its size is right - left + 1) and an array of integer queries. For each query q, find the size of the smallest interval with left <= q <= right, or -1 if none contains it. Return the answers in query order.

Example

Text

Input:  intervals = [[1,3],[2,3],[3,7],[6,6]], queries = [2,3,6]    Output: [2, 2, 1]
Input:  intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]    Output: [2, -1, 4, 6]

Brute force: scan every interval for every query

For each query, look at all intervals, keep those containing it, and take the smallest size. -1 stands for "no interval contains it".

Java

import java.util.Arrays;

class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        int[] answers = new int[queries.length];
        for (int k = 0; k < queries.length; k++) {
            int q = queries[k];
            int best = -1;
            for (int[] iv : intervals) {
                if (iv[0] <= q && q <= iv[1]) {
                    int size = iv[1] - iv[0] + 1;
                    if (best == -1 || size < best) {
                        best = size;
                    }
                }
            }
            answers[k] = best;
        }
        return answers;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.minInterval(
                new int[][] {{1, 3}, {2, 3}, {3, 7}, {6, 6}}, new int[] {2, 3, 6})));
        System.out.println(Arrays.toString(solution.minInterval(
                new int[][] {{2, 3}, {2, 5}, {1, 8}, {20, 25}}, new int[] {2, 19, 5, 22})));
        System.out.println(Arrays.toString(solution.minInterval(new int[][] {}, new int[] {1})));
    }
}

Output

[2, 2, 1]
[2, -1, 4, 6]
[-1]

Time: O(n · q). Space: O(q) for the answers.

Optimal: offline sweep with a min-heap

Answer the queries in increasing order (remembering their original positions), and sort the intervals by left end. Keep a min-heap of {size, right} for every interval that has started (left <= q) so far:

Push all intervals with left <= q onto the heap.
Poll from the top while the smallest interval has right < q: it ended before this query, and since queries only grow it can never help again.
The top of the heap, if any, is the smallest interval containing q.

Expired intervals that are not at the top stay in the heap until they reach it, so lazy deletion is enough. PriorityQueue is a min-heap, ordered here by size and then by right end. To sort query positions by query value, the code sorts an Integer[] of indices with a comparator, because Arrays.sort with a comparator needs object elements.

Java

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

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

        // Each entry is {size, right}.
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) ->
                a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
        int[] answers = new int[queries.length];
        Arrays.fill(answers, -1);
        int next = 0;
        for (int idx : order) {
            int q = queries[idx];
            while (next < sorted.length && sorted[next][0] <= q) {
                int l = sorted[next][0];
                int r = sorted[next][1];
                heap.add(new int[] {r - l + 1, r});
                next++;
            }
            while (!heap.isEmpty() && heap.peek()[1] < q) {
                heap.poll();
            }
            if (!heap.isEmpty()) {
                answers[idx] = heap.peek()[0];
            }
        }
        return answers;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.minInterval(
                new int[][] {{1, 3}, {2, 3}, {3, 7}, {6, 6}}, new int[] {2, 3, 6})));
        System.out.println(Arrays.toString(solution.minInterval(
                new int[][] {{2, 3}, {2, 5}, {1, 8}, {20, 25}}, new int[] {2, 19, 5, 22})));
        System.out.println(Arrays.toString(solution.minInterval(new int[][] {}, new int[] {1})));
    }
}

Output

[2, 2, 1]
[2, -1, 4, 6]
[-1]

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

Each interval is pushed once and polled at most once, so the heap work is O(n log n); sorting the queries costs O(q log q).