The problem
An interval [left, right] has size right − left + 1. For each number in queries, return the size of the smallest interval containing it, or −1 if none does.
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]
Constraints
- 1 ≤ intervals.length, queries.length ≤ 10⁵
- 1 ≤ left ≤ right ≤ 10⁷
- 1 ≤ queries[j] ≤ 10⁷
The idea
Checking every interval for every query is 10¹⁰ steps. Instead answer the queries in increasing order, and sort the intervals by their left end; then intervals only ever join the candidates and leave them, each once.
For a query x: add every interval that starts at or before x to a min-heap ordered by size. Some in the heap may already have ended before x; the smallest-first order means only the top matters, so pop the top while it has ended — it is useless for every later, larger query too. What remains on top is the smallest interval holding x. Answers are written back in the queries’ original order.
- Time
- O(n log n + q log q)
- Space
- O(n + q)
Solution · every language run against every case
class Solution: def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]: intervals.sort() answer = [-1] * len(queries) heap = [] # (size, right end) of intervals that have started i = 0 # Answer the queries from smallest to largest, so intervals only ever join and leave. for q in sorted(range(len(queries)), key=lambda k: queries[k]): x = queries[q] while i < len(intervals) and intervals[i][0] <= x: # every interval starting by x l, r = intervals[i] heappush(heap, (r - l + 1, r)) i += 1 while heap and heap[0][1] < x: # ended before x: useless now and for every later query heappop(heap) if heap: answer[q] = heap[0][0] # the smallest interval holding x return answer