Minimum Interval to Include Each Query
HardUpdated: Aug 2, 2025
Practice on:
Problem
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
Example 1:
Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3.
- Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3.
- Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1.
- Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.
Example 2:
Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
Output: [2,-1,4,6]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2.
- Query = 19: None of the intervals contain 19. The answer is -1.
- Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4.
- Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.
Solution
Method 1 - Sort the intervals
To solve this problem efficiently:
- Sort intervals and queries:
- Sort intervals by their start point (
left) and then by their size (right - left), as smaller intervals should be preferred when resolving queries. - Sort queries, keeping track of their original indices, so we can return results in the original order.
- Sort intervals by their start point (
- Use a min-heap to track active intervals:
- Use a min-heap to maintain active intervals. The heap will store intervals sorted by size.
- As we iterate over queries, add intervals to the heap when their start (
left) is less than or equal to the current query. - Remove intervals from the heap if their end (
right) is less than the current query.
- Answer each query:
- For each query, examine the smallest interval in the heap. If it's valid (covers the current query), use its size as the answer.
- If no valid interval exists, return
-1for that query.
Code
Java
public class Solution {
public int[] minInterval(int[][] intervals, int[] queries) {
// Sort intervals by start, then by size
Arrays.sort(intervals, (a, b) -> {
int cmp = Integer.compare(a[0], b[0]);
return cmp == 0 ? Integer.compare((a[1] - a[0] + 1), (b[1] - b[0] + 1)) : cmp;
});
// Pair queries with their original indices and sort by query value
int[][] indexedQueries = new int[queries.length][2];
for (int i = 0; i < queries.length; i++) {
indexedQueries[i] = new int[]{queries[i], i};
}
Arrays.sort(indexedQueries, Comparator.comparingInt(a -> a[0]));
PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0])); // Min-heap
int[] ans = new int[queries.length];
Arrays.fill(ans, -1);
int i = 0; // Pointer for intervals
for (int[] query : indexedQueries) {
int q = query[0];
int idx = query[1];
// Add intervals to the heap whose start <= current query
while (i < intervals.length && intervals[i][0] <= q) {
int left = intervals[i][0];
int right = intervals[i][1];
heap.offer(new int[]{right - left + 1, right, left});
i++;
}
// Remove intervals from the heap whose end < current query
while (!heap.isEmpty() && heap.peek()[1] < q) {
heap.poll();
}
// Use the heap's smallest interval if it covers the current query
if (!heap.isEmpty() && heap.peek()[2] <= q && q <= heap.peek()[1]) {
ans[idx] = heap.peek()[0];
}
}
return ans;
}
}
Python
class Solution:
def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
# Sort intervals by start, then by size
intervals.sort(key=lambda x: (x[0], x[1] - x[0] + 1))
# Sort queries, tracking original indices
indexed_queries = sorted(enumerate(queries), key=lambda x: x[1])
heap = [] # Min-heap to store intervals by size
i = 0 # Pointer for intervals
ans: List[int] = [-1] * len(queries) # Result array
for idx, q in indexed_queries:
# Add intervals to the heap whose start <= current query
while i < len(intervals) and intervals[i][0] <= q:
left, right = intervals[i]
heapq.heappush(heap, (right - left + 1, right, left))
i += 1
# Remove intervals from the heap whose end < current query
while heap and heap[0][1] < q:
heapq.heappop(heap)
# Use the heap's smallest interval if it covers the current query
if heap and heap[0][2] <= q <= heap[0][1]:
ans[idx] = heap[0][0]
return ans
Complexity
- ⏰ Time complexity:
O(n * log(n) + m * log(m))- Sorting intervals and queries:
O(n * log(n) + m * log(m))wherenis the number of intervals andmis the number of queries. - Adding to/removing from the heap: Each interval is added/removed once, so it's
O(n * log(n)). - Query processing: Each query involves heap operations and interval additions/removals, totalling
O(m * log(n)). - Total Time Complexity:
O(n * log(n) + m * log(m)).
- Sorting intervals and queries:
- 🧺 Space complexity:
O(n + m)- Min-heap: Stores up to
nintervals, soO(n)space. - Sorting indices:
O(m)for tracking query indices. - Total Space Complexity:
O(n + m).
- Min-heap: Stores up to