Minimum Interval to Include Each Query

Master this topic with zero to advance depth.

Minimum Interval to Include Each Query

You are given a 2D integer array intervals, where intervals[i] = [left_i, right_i] represents an inclusive interval [left_i, right_i]. You are also given an integer array queries.

The answer to the jth query is the size of the smallest interval i such that left_i <= queries[j] <= right_i. The size of an interval is equal to right_i - left_i + 1.

Return an array containing the answers to the queries.

Visual Representation

intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]

Query 2: Intervals covering 2 -> [1,4](size 4), [2,4](size 3). Min = 3
Query 3: Intervals covering 3 -> [1,4](size 4), [2,4](size 3), [3,6](size 4). Min = 3
Query 4: Intervals covering 4 -> [1,4](size 4), [2,4](size 3), [3,6](size 4), [4,4](size 1). Min = 1
Query 5: Intervals covering 5 -> [3,6](size 4). Min = 4

Hard

Examples

Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]

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

Approach 1

Level I: Brute Force - Check Every Interval Per Query

Intuition

For each query, scan all intervals to find which ones contain the query point. Among all covering intervals, choose the one with the minimum size. If no interval covers the query, return -1.

⏱ O(N * Q) where N is the number of intervals and Q is the number of queries💾 O(1) extra besides the output array

Detailed Dry Run

intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5] Query 2: [1,4] covers 2? Yes. Size = 4 [2,4] covers 2? Yes. Size = 3 [3,6] covers 2? No. [4,4] covers 2? No. Min = 3 Query 4: All 4 cover 4. Min = [4,4].size = 1

java

public class Main {
    public static int[] minInterval(int[][] intervals, int[] queries) {
        int n = queries.length;
        int[] ans = new int[n];
        
        for (int j = 0; j < n; j++) {
            int q = queries[j];
            int minSize = Integer.MAX_VALUE;
            for (int[] interval : intervals) {
                if (interval[0] <= q && q <= interval[1]) {
                    int size = interval[1] - interval[0] + 1;
                    minSize = Math.min(minSize, size);
                }
            }
            ans[j] = minSize == Integer.MAX_VALUE ? -1 : minSize;
        }
        return ans;
    }

    public static void main(String[] args) {
        int[][] iv = {{1,4},{2,4},{3,6},{4,4}};
        int[] q = {2,3,4,5};
        int[] res = minInterval(iv, q);
        System.out.println(java.util.Arrays.toString(res)); // [3, 3, 1, 4]
    }
}

Approach 2

Level II: Sort Intervals by Size and Scan

Intuition

To optimize the search for the smallest interval, we can pre-sort all intervals by their size (right - left + 1). For each query, we then scan the sorted intervals and return the first one that contains the query point. Since the intervals are sorted by size, the first valid interval we find is guaranteed to be the smallest.

⏱ O(N log N + Q * N) where N is the number of intervals and Q is the number of queries💾 O(N) to store the sorted intervals

Detailed Dry Run

intervals = [[1,4],[2,4],[3,6],[4,4]], q = 2 Sizes: [1,4]->4, [2,4]->3, [3,6]->4, [4,4]->1 Sorted by Size: [[4,4], [2,4], [1,4], [3,6]] Query 2: [4,4] covers 2? No. [2,4] covers 2? Yes. STOP. ans = 3. Query 4: [4,4] covers 4? Yes. STOP. ans = 1.

java

import java.util.*;

public class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        int n = queries.length;
        int[][] sortedIv = new int[intervals.length][3];
        for (int i = 0; i < intervals.length; i++) {
            sortedIv[i][0] = intervals[i][0];
            sortedIv[i][1] = intervals[i][1];
            sortedIv[i][2] = intervals[i][1] - intervals[i][0] + 1;
        }
        
        Arrays.sort(sortedIv, (a, b) -> Integer.compare(a[2], b[2]));
        
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int q = queries[i];
            ans[i] = -1;
            for (int[] iv : sortedIv) {
                if (iv[0] <= q && q <= iv[1]) {
                    ans[i] = iv[2];
                    break;
                }
            }
        }
        return ans;
    }
}

Approach 3

Level III: Sort + Min-Heap (Sweep Line Approach)

Intuition

Sort both the intervals (by start) and the queries (by value). Use a pointer on intervals and a Min-Heap ordered by interval size.

Process each sorted query:

Add all intervals whose start <= current query to the Min-Heap (they might cover this query).
Remove all intervals from the top of the heap whose end < current query (they expired).
The top of the heap (if any) is the smallest valid interval covering the query.

We must store results keyed by the original query index to return answers in the right order.

⏱ O(N log N + Q log Q + (N+Q) log N) — dominated by sorting and heap operations💾 O(N + Q) for the heap and result map

Detailed Dry Run

iv = [[1,4],[2,4],[3,6],[4,4]], q = [2,3,4,5] Sort intervals by start: [[1,4],[2,4],[3,6],[4,4]] Sort queries with orig idx: [(2,0),(3,1),(4,2),(5,3)] MinHeap sorted by size (right-left+1) ptr=0

q=2: Add 1,4, 2,4. Heap=[(3,[2,4]),(4,[1,4])]. Top=3. ans[0]=3. q=3: Add 3,6. Heap=tops. Remove [2,4] as 4>=3. Top=1,4. ans[1]=3? Let's re-check. Actually heap=[(3,[2,4]),(4,[1,4]),(4,[3,6])]. 2,4 still covers 3. ans[1]=3. q=4: Add 4,4. Heap=[(1,[4,4]),...]. Remove expired: checks 2,4 (4>=4, valid), 1,4 (4>=4, valid), 3,6 (6>=4, valid). Top=4,4. ans[2]=1. q=5: No new. Remove [2,4](4<5 expired). Remove [1,4](4<5 expired). [3,6](6>=5 ok), [4,4](4<5 expired). Heap=[(4,[3,6])]. ans[3]=4.

java

import java.util.*;

public class Main {
    public static int[] minInterval(int[][] intervals, int[] queries) {
        int n = queries.length;
        int[] ans = new int[n];
        
        // Sort intervals by start
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        
        // Sort queries but keep original indices
        Integer[] qIdx = new Integer[n];
        for (int i = 0; i < n; i++) qIdx[i] = i;
        Arrays.sort(qIdx, (a, b) -> queries[a] - queries[b]);
        
        // Min-Heap: {size, end}
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int ptr = 0;
        
        for (int i : qIdx) {
            int q = queries[i];
            
            // Add all intervals starting <= q
            while (ptr < intervals.length && intervals[ptr][0] <= q) {
                int size = intervals[ptr][1] - intervals[ptr][0] + 1;
                heap.offer(new int[]{size, intervals[ptr][1]});
                ptr++;
            }
            
            // Remove intervals that ended before q
            while (!heap.isEmpty() && heap.peek()[1] < q) {
                heap.poll();
            }
            
            ans[i] = heap.isEmpty() ? -1 : heap.peek()[0];
        }
        
        return ans;
    }

    public static void main(String[] args) {
        int[][] iv = {{1,4},{2,4},{3,6},{4,4}};
        int[] q = {2,3,4,5};
        System.out.println(Arrays.toString(minInterval(iv, q))); // [3, 3, 1, 4]
    }
}

← Previous QuestionMaximum Performance of a Team

Next Question →Maximum Number of Events

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.