Minimum Interval to Include Each Query
You're given a list of closed intervals [left, right] and a list of integer queries. The size of an interval is right - left + 1, the number of integers it contains. For each query q, find the smallest size among the intervals with left <= q <= right, or -1 if no interval contains q. Return the answers in the order of the queries.
Examples
intervals = [[2,5],[4,4],[1,8]], queries = [4,7,9] returns [1,8,-1]
Query 4 sits in all three intervals, and [4,4] has size 1. Query 7 sits only in [1,8], of size 8. No interval reaches 9.
intervals = [[3,6],[5,9]], queries = [6,3,10] returns [4,4,-1]
Queries 6 and 3 both fall in [3,6], of size 4. The answers keep the original query order.
intervals = [[1,10],[5,6]], queries = [5,2] returns [2,10]
Query 5 is in both intervals and takes the smaller, [5,6]. Query 2 is only in [1,10].
Constraints
- 1 <= intervals.length, queries.length <= 10^5
- 1 <= left <= right <= 10^7
- 1 <= queries[j] <= 10^7
Hints
Checking every interval for every query is O(n * k). Would it help to handle the queries in sorted order?
As the query value grows, an interval starts to contain it once left <= q and stops for good once right < q. A min-heap keyed by size can hold the candidates.
Sort the intervals by left and the queries by value, keeping original indices. For each query, push (size, right) for every interval with left <= q, pop while the top's right < q, then record the top's size or -1.
Drill This: Your Approach First
Approach
Answer the queries offline, in increasing order. Sort the intervals by left end and sort the query indices by query value. Sweep through the queries with a min-heap of (size, right) pairs. Before answering q, push every interval whose left <= q, then pop from the top while its right < q: an interval that ends before q also ends before every later query, so it is safe to discard for good. The top of the heap is then the smallest interval containing q, or the heap is empty and the answer is -1. Write each answer at its query's original index. O(n log n + k log k) time for n intervals and k queries, and O(n + k) space.
Time
O(n log n + k log k)
Space
O(n + k)
Pitfall
Solutions
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, (a, b) -> Integer.compare(queries[a], queries[b]));
// Heap entries: [size, right], smallest size first.
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
int[] ans = new int[queries.length];
int next = 0;
for (int idx : order) {
int q = queries[idx];
while (next < sorted.length && sorted[next][0] <= q) {
heap.add(new int[]{sorted[next][1] - sorted[next][0] + 1, sorted[next][1]});
next++;
}
while (!heap.isEmpty() && heap.peek()[1] < q) heap.poll();
ans[idx] = heap.isEmpty() ? -1 : heap.peek()[0];
}
return ans;
}
}import heapq
class Solution:
def minInterval(self, intervals, queries):
intervals = sorted(intervals)
ans = [-1] * len(queries)
heap = [] # (size, right)
nxt = 0
for idx in sorted(range(len(queries)), key=lambda i: queries[i]):
q = queries[idx]
while nxt < len(intervals) and intervals[nxt][0] <= q:
left, right = intervals[nxt]
heapq.heappush(heap, (right - left + 1, right))
nxt += 1
while heap and heap[0][1] < q:
heapq.heappop(heap)
if heap:
ans[idx] = heap[0][0]
return ans