Skip to content
AI360Xpert
Back to Intervals
Hard

Minimum Interval to Include Each Query

You are given a 2D integer array `intervals`, where `intervals[i] = [lefti, righti]` describes the `ith` interval starting at `lefti` and ending at `righti` (inclusive). The size of an interval is defined as the number of integers it contains, or more formally `righti - lefti + 1`. You are also given an integer array `queries`. The answer to the `jth` query is the size of the smallest interval `i` such that `lefti <= queries[j] <= righti`. If no such interval exists, the answer is `-1`. Return an array containing the answers to the queries.

Examples

Input:intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output:[3,3,1,4]
The queries are processed as follows: - Query = 2: The interval [2,4] is the smallest interval containing 2. Size is 4 - 2 + 1 = 3. - Query = 3: The interval [2,4] is the smallest interval containing 3. Size is 4 - 2 + 1 = 3. - Query = 4: The interval [4,4] is the smallest interval containing 4. Size is 4 - 4 + 1 = 1. - Query = 5: The interval [3,6] is the smallest interval containing 5. Size is 6 - 3 + 1 = 4.
Input:intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
Output:[2,-1,4,6]
The queries are processed as follows: - Query = 2: The interval [2,3] is the smallest. Size is 2. - Query = 19: None of the intervals contain 19. Size is -1. - Query = 5: The interval [2,5] is the smallest. Size is 4. - Query = 22: The interval [20,25] is the smallest. Size is 6.

Constraints

  • 1 <= intervals.length <= 10^5
  • 1 <= queries.length <= 10^5
  • intervals[i].length == 2
  • 1 <= lefti <= righti <= 10^7
  • 1 <= queries[j] <= 10^7

Min-Heap and Offline Queries

Approach

To process queries efficiently, we can sort both the intervals (by start time) and the queries. However, we need to remember the original order of the queries to return the result correctly, so we pair each query with its original index. We iterate through the sorted queries. For each query, we add all intervals that start before or at the query's value into a min-heap. The heap is ordered by the size of the interval. Before extracting the minimum size from the heap, we remove any intervals from the top of the heap that end before the current query's value (since they can no longer cover this or any future queries). If the heap is not empty, the top element is the smallest valid interval. If it is empty, the answer is `-1`.

Complexity Analysis

Time Complexity
O(N log N + Q log Q)
Space Complexity
O(N + Q)

Sorting intervals takes O(N log N) and sorting queries takes O(Q log Q). Heap operations take O(log N) for each of the N intervals. Total time complexity is dominated by sorting and heap operations. Space complexity is O(N + Q) to store the sorted queries, the result mapping, and the heap.

Solution.java
class Solution {    public int[] minInterval(int[][] intervals, int[] queries) {        int[] res = new int[queries.length];                // Sort intervals by start time        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));                // Create an array of queries with their original indices        int[][] sortedQueries = new int[queries.length][2];        for (int i = 0; i < queries.length; i++) {            sortedQueries[i][0] = queries[i];            sortedQueries[i][1] = i;        }                // Sort queries by value        Arrays.sort(sortedQueries, (a, b) -> Integer.compare(a[0], b[0]));                // Min-heap: stores {interval_size, interval_end}        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));                int i = 0;        for (int[] q : sortedQueries) {            int queryVal = q[0];            int originalIdx = q[1];                        // Add all intervals that start before or at the query value            while (i < intervals.length && intervals[i][0] <= queryVal) {                int size = intervals[i][1] - intervals[i][0] + 1;                minHeap.offer(new int[]{size, intervals[i][1]});                i++;            }                        // Remove intervals from heap that end before the query value            while (!minHeap.isEmpty() && minHeap.peek()[1] < queryVal) {                minHeap.poll();            }                        // If heap is not empty, the top is the smallest valid interval            res[originalIdx] = minHeap.isEmpty() ? -1 : minHeap.peek()[0];        }                return res;    }}