Core Insight After sorting, overlap decisions depend only on the active interval and the next start.
Common Pitfall Compare the next start against the current end, not against the original unsorted input.
Description
For each query, find size of smallest interval containing query point.
Constraints
- Time Complexity:
O((n+q) log n) - Space Complexity:
O(n+q)
Tags
arraybinary-searchsortingheapsliding-window
Implementation Plan Translate the invariant into these small, testable moves.
- Sort by the relevant endpoint.
- Initialize the active interval.
- Merge or select based on overlap.
- Update the active boundary.
def minInterval(intervals, queries):
intervals.sort()
minHeap = []
res = {}
i = 0
for q in sorted(queries):
while i < len(intervals) and intervals[i][0] <= q:
l, r = intervals[i]
heapq.heappush(minHeap, (r - l + 1, r))
i += 1
while minHeap and minHeap[0][1] < q:
heapq.heappop(minHeap)
res[q] = minHeap[0][0] if minHeap else -1
return [res[q] for q in queries]