Minimum Interval to Include Each Query
Problem
Given a list of intervals and a list of queries, return an array where each element is the size of the smallest interval that contains the corresponding query, or -1 if no such interval exists.
- 1 ≤ intervals.length ≤ 10⁵
- 1 ≤ queries.length ≤ 10⁵
- intervals[i].length == 2
- 1 ≤ intervals[i][0] ≤ intervals[i][1] ≤ 10⁷
- 1 ≤ queries[i] ≤ 10⁷
Example
intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5][3,3,1,4]Sort intervals by start: [[1,4],[2,4],[3,6],[4,4]]. For query 2, intervals [1,4] and [2,4] contain it; smallest size is 4-1+1=4 and 4-2+1=3, so 3 is chosen. For query 3, intervals [1,4],[2,4],[3,6] contain it; smallest size is 3 again. For query 4, intervals [1,4],[2,4],[3,6],[4,4] contain it; smallest size is 1 (from [4,4]). For query 5, only [3,6] contains it with size 4.
Approach
Straightforward Solution
A naive approach checks each query against all intervals to find the minimal containing interval, resulting in O(n*m) time complexity (n = intervals, m = queries), which is infeasible for large inputs.
Core Observation
The smallest interval containing a query is the interval with the minimal length that covers the query point. Intervals can overlap, so multiple intervals may contain the same query. Efficiently finding the minimal such interval for each query requires a data structure that can dynamically track candidate intervals as queries progress.
Path to Optimal
Sorting intervals by their start points and queries in ascending order allows processing intervals and queries in a coordinated manner. Using a min-heap keyed by interval size enables efficient retrieval of the smallest interval currently covering the query. For each query, intervals starting before or at the query are pushed onto the heap. Intervals ending before the query are popped off, ensuring the heap only contains intervals covering the query. The top of the heap then gives the minimal interval size.
Optimal Approach
Sort intervals by start. Sort queries. Iterate queries in ascending order, pushing intervals starting before or at the query onto a min-heap keyed by interval size and end. Pop intervals from the heap that end before the query. If the heap is not empty, the top element corresponds to the smallest interval containing the query. Store this result in a map keyed by query. Finally, return results in the original query order.
Time
O((n + m) log n)
Sorting intervals and queries takes O(n log n) and O(m log m) respectively. Each interval is pushed and popped at most once from the heap, each operation O(log n). Each query is processed once, resulting in O(m log n) for heap operations. Overall complexity is O((n + m) log n).
Space
O(n)
The min-heap stores intervals that are candidates for queries. In the worst case, all intervals may be in the heap simultaneously, requiring O(n) auxiliary space.
Pattern Spotlight
Heap / Priority Queue (Dynamic Candidate Filtering)
When needing to find the minimal or maximal element among dynamically changing candidates constrained by a moving parameter (like a query), use a heap to efficiently add candidates as they become relevant and remove those that become invalid, ensuring the top of the heap always reflects the current optimal choice.
Solution
| 1 | import heapq
|
| 2 |
|
| 3 | class Solution:
|
| 4 | def minInterval(self, intervals: list[list[int]], queries: list[int]) -> list[int]:
|
| 5 | intervals.sort()
|
| 6 |
|
| 7 | min_heap = []
|
| 8 | res = {}
|
| 9 | i = 0
|
| 10 |
|
| 11 | for q in sorted(queries):
|
| 12 | while i < len(intervals) and intervals[i][0] <= q:
|
| 13 | l, r = intervals[i]
|
| 14 | heapq.heappush(min_heap, (r - l + 1, r))
|
| 15 | i += 1
|
| 16 |
|
| 17 | while min_heap and min_heap[0][1] < q:
|
| 18 | heapq.heappop(min_heap)
|
| 19 |
|
| 20 | if min_heap:
|
| 21 | res[q] = min_heap[0][0]
|
| 22 | else:
|
| 23 | res[q] = -1
|
| 24 |
|
| 25 | return [res[q] for q in queries] |
Step-by-Step Solution
Sort Intervals to Enable Sequential Processing by Start Point
| 5 | intervals.sort()
|
Objective
To arrange intervals in ascending order by their start points to facilitate efficient incremental processing alongside sorted queries.
Key Insight
Sorting intervals by start allows the algorithm to process intervals in a single pass, pushing only those intervals that could possibly contain the current query. This ordering is essential to avoid repeatedly scanning all intervals for each query, reducing complexity from O(n*m) to O(n log n + m log n).
Interview Quick-Check
Core Logic
Sorting intervals by start ensures that when processing queries in ascending order, intervals can be added to the heap exactly once when their start is less than or equal to the query.
Common Pitfalls & Bugs
Failing to sort intervals leads to repeated scanning or incorrect heap contents, causing inefficiency or incorrect results.
Iterate Queries in Sorted Order, Adding Relevant Intervals to Min-Heap
| 11 | for q in sorted(queries):
|
| 12 | while i < len(intervals) and intervals[i][0] <= q:
|
| 13 | l, r = intervals[i]
|
| 14 | heapq.heappush(min_heap, (r - l + 1, r))
|
| 15 | i += 1
|
Objective
To process queries in ascending order, pushing intervals that start before or at the query onto a min-heap keyed by interval size and end point.
Key Insight
By iterating queries in ascending order, intervals can be added to the heap in a single pass as they become relevant. The min-heap keyed by interval size ensures that the smallest interval containing the query is always at the top. This dynamic candidate filtering avoids redundant checks and leverages the heap's O(log n) insertion and removal.
Interview Quick-Check
Core Logic
For each query, push all intervals starting before or at the query onto the heap, ensuring the heap contains all candidate intervals that might cover the query.
State & Boundaries
Use a pointer to track the current interval index, advancing it as intervals are added to the heap.
Common Pitfalls & Bugs
Not advancing the interval pointer correctly can cause infinite loops or missed intervals.
Remove Intervals from Heap That Do Not Cover Current Query
| 17 | while min_heap and min_heap[0][1] < q:
|
| 18 | heapq.heappop(min_heap)
|
Objective
To discard intervals from the heap whose end points are less than the current query, ensuring only intervals containing the query remain.
Key Insight
Intervals ending before the query cannot contain it, so removing them maintains heap integrity and correctness. This step guarantees that the heap top always corresponds to the smallest interval that covers the query, enabling immediate retrieval of the answer.
Interview Quick-Check
Core Logic
Pop intervals from the heap while their end is less than the query, filtering out invalid candidates.
Common Pitfalls & Bugs
Failing to remove expired intervals leads to incorrect answers, as the heap top may represent an interval that does not contain the query.
Record the Smallest Interval Size or -1 for Each Query
| 20 | if min_heap:
|
| 21 | res[q] = min_heap[0][0]
|
| 22 | else:
|
| 23 | res[q] = -1
|
Objective
To store the size of the smallest interval containing the query if any exist, or -1 if none do.
Key Insight
After filtering, if the heap is non-empty, the top element corresponds to the smallest interval covering the query. Recording this value in a dictionary keyed by query allows retrieval in original query order. If the heap is empty, no interval covers the query, so -1 is recorded.
Interview Quick-Check
Core Logic
Use the heap top's interval size as the answer for the query if available; otherwise, assign -1.
State & Boundaries
Store results in a map keyed by query to preserve answers for queries processed out of original order.
Return Results in Original Query Order
| 25 | return [res[q] for q in queries] |
Objective
To produce the final output array by mapping each original query to its computed minimal interval size or -1.
Key Insight
Since queries were processed in sorted order, results are stored in a dictionary keyed by query value. Returning results in the original order requires iterating over the original queries and retrieving their answers from the dictionary, ensuring output matches input order.
Interview Quick-Check
Core Logic
Map each original query to its precomputed answer to maintain correct output order.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
while i < len(intervals) and intervals[i][0] <= q:While intervals start before or at the query, add them to the heap.
This loop adds all intervals that could potentially cover the current query, ensuring the heap contains all relevant candidates.
heapq.heappush(min_heap, (r - l + 1, r))Push the interval onto the min-heap keyed by size and end point.
Heap ordering by interval size ensures the smallest interval containing the query is always accessible at the top.
while min_heap and min_heap[0][1] < q:Remove intervals from the heap that end before the query.
Discarding intervals that cannot contain the query maintains heap correctness and ensures the top interval is valid.
res[q] = min_heap[0][0]Assign the smallest interval size to the query's result.
The heap top corresponds to the minimal interval containing the query, providing the correct answer.
intervals.sort()Sort intervals by their start points in ascending order.
Sorting intervals enables efficient incremental processing alongside sorted queries, allowing intervals to be added to the heap exactly once when relevant.
min_heap = []Initialize an empty min-heap to store candidate intervals.
The min-heap maintains intervals keyed by their size and end point, enabling efficient retrieval of the smallest interval covering the current query.
heapq.heappop(min_heap)Pop the top interval from the heap.
Removing invalid intervals prevents incorrect answers and keeps the heap size manageable.
i = 0Initialize an index pointer to track intervals processed.
This pointer ensures each interval is pushed onto the heap exactly once when its start is less than or equal to the current query.
for q in sorted(queries):Iterate over queries in ascending order.
Processing queries in sorted order allows incremental addition of intervals to the heap and efficient filtering of invalid intervals.
i += 1Advance the interval pointer after pushing.
Incrementing the pointer prevents reprocessing intervals and maintains correct heap state.
if min_heap:Check if the heap is non-empty after filtering.
Determines if any interval covers the current query, guiding result assignment.
else:Handle the case where no interval covers the query.
Assigning -1 signals that the query is not contained in any interval, fulfilling problem requirements.
return [res[q] for q in queries]Return the results in the original query order.
Mapping back to original query order ensures output matches input, as queries were processed sorted.
res = {}Initialize a dictionary to store results for each query.
Storing results keyed by query allows retrieval in original query order after processing queries in sorted order.
res[q] = -1Store the result for the current query in the dictionary.
Mapping results by query value allows retrieval in original order after processing.
l, r = intervals[i]Extract the start and end of the current interval.
Decomposing the interval allows calculation of its size and management in the heap.
Test Your Understanding
Why does the algorithm remove intervals from the heap that end before the current query?
Because intervals that end before the query cannot contain the query, so they are no longer valid candidates and must be removed to ensure the heap top always corresponds to intervals that cover the query.
Related Problems
Heaps pattern
Don't just read it. Drill it.
Reconstruct Minimum Interval to Include Each Query from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Minimum Interval to Include Each Query drill