Minimum Interval to Include Each Query
The key idea
Sort queries ascending and process them in that order. Sweep the intervals (also sorted by start) into a min-heap keyed by interval size as their start passes the current query. Lazily pop heap entries whose end has fallen behind the query — the heap top is then the smallest interval still covering it.
Problem
You are given a 2D integer array intervals, where intervals[i] = [lefti, righti] describes the i-th interval starting at lefti and ending at righti (both inclusive). The size of an interval is the number of integers it contains, which is equal to righti - lefti + 1.
You are also given an integer array queries. The answer to the j-th 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.
Constraints
1 <= intervals.length <= 10^51 <= queries.length <= 10^5intervals[i].length == 21 <= lefti <= righti <= 10^71 <= queries[j] <= 10^7
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]
Complexity
Time: O((n + q) log(n + q)) where n = intervals, q = queries Space: O(n + q)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Heap / Priority Queue problems
- Find K Pairs with Smallest SumsMEDIUM
- Find Median from Data StreamHARD
- IPOHARD
- K Closest Points to OriginMEDIUM
- Kth Largest Element in a StreamEASY
- Kth Largest Element in an ArrayMEDIUM
- Last Stone WeightEASY
- Maximum Subsequence ScoreMEDIUM
- Meeting Rooms IIMEDIUM
- Meeting Rooms IIIHARD
- Merge k Sorted ListsHARD
- Single-Threaded CPUMEDIUM