Intervals - Minimum Interval to Include Each Query
Examine the following buggy code snippet for the minimum interval problem. Which line contains the subtle bug that can cause incorrect results on some inputs?
def min_interval_binary_search(intervals, queries):
intervals.sort(key=lambda x: x[1] - x[0] + 1)
lengths = [end - start for start, end in intervals]
starts = [start for start, end in intervals]
ends = [end for start, end in intervals]
def covers(query, length):
idx = bisect.bisect_right(lengths, length)
for i in range(idx):
if starts[i] <= query <= ends[i]:
return True
return False
res = []
max_len = lengths[-1] if lengths else 0
for q in queries:
left, right = 1, max_len
ans = -1
while left <= right:
mid = (left + right) // 2
if covers(q, mid):
ans = mid
right = mid - 1
else:
left = mid + 1
res.append(ans)
return res