Hard Sort + Heap Intervals
In plain English: For each query value, find the smallest interval (by length) that contains it.
Sort intervals by start and queries by value. Sweep through queries in order, pushing applicable intervals onto a min-heap keyed by size. Pop expired intervals. The heap top is the smallest valid interval.
Prompt
Given a 2D array intervals and a queries array, for each query return the size of the smallest interval that contains the query. Return -1 if no interval contains it.
Try to write it from scratch before scrolling down.
Solution
import heapq
def min_interval(intervals, queries):
intervals.sort()
result = {}
heap = [] # (size, end)
i = 0
for q in sorted(set(queries)):
# push all intervals that start <= q
while i < len(intervals) and intervals[i][0] <= q:
lo, hi = intervals[i]
heapq.heappush(heap, (hi - lo + 1, hi))
i += 1
# pop intervals that ended before q
while heap and heap[0][1] < q:
heapq.heappop(heap)
result[q] = heap[0][0] if heap else -1
return [result[q] for q in queries]
# Test: min_interval([[1,4],[2,4],[3,6],[4,4]], [2,3,4,5])
# == [3,3,1,4]