Description
For each query value, return the size of the shortest closed interval containing it, or -1 if none does. Interval [left, right] has size right - left + 1; preserve query order.
Solution
import heapq
def min_interval(intervals, queries):
ordered = sorted(intervals)
answer = [-1] * len(queries)
heap = []
index = 0
for query, original in sorted((value, i) for i, value in enumerate(queries)):
while index < len(ordered) and ordered[index][0] <= query:
left, right = ordered[index]
heapq.heappush(heap, (right - left + 1, right))
index += 1
while heap and heap[0][1] < query:
heapq.heappop(heap)
if heap:
answer[original] = heap[0][0]
return answerExamples
Example 1
- Input
[[[1,4],[2,4],[3,6],[4,4]],[2,3,4,5]]- Output
[3,3,1,4]
Query 4 fits the one-point interval.
Example 2
- Input
[[[2,3],[2,5],[1,8],[20,25]],[2,19,5,22]]- Output
[2,-1,4,6]
19 is not covered.
Example 3
- Input
[[[1,1]],[1,1,2]]- Output
[1,1,-1]
Repeated queries receive the same answer.
Approach
Sort intervals by start and queries by value. Before each query, add every interval already started to a min-heap keyed by length. Remove expired heap roots, then read the shortest remaining candidate. Store the result at the query's original index.
Time & space
O(n log n + q log q + (n + q) log(n + 1)) time and O(n + q) auxiliary space, where n is interval count and q is query count.