寻找包含 Python 中每个查询的最小间隔的程序
假设我们有一个区间列表，其中区间[i]有一对(left_i,right_i)表示第i个区间，从left_i开始到right_i结束（两者都包括在内）。我们还有另一个称为查询的数组。第j个查询的答案是最小区间i的大小，使得left_i<=queries[j]<=right_i。如果我们找不到这样的区间，则返回-1。我们必须找到一个包含查询答案的数组。
因此，如果输入类似于intervals=[[2,5],[3,5],[4,7],[5,5]]queries=[3,4,5,6]，那么输出将是[3,3,1,4]，因为查询处理如下-
对于query=3：区间[3,5]是最小的一个，包含3。所以，5-3+1=3。
forquery=4：区间[3,5]是最小的一个，包含4。所以，5-3+1=3。
forquery=5：区间[5,5]是最小的一个，包含5。所以，5-5+1=1。
对于query=6：区间[4,7]是最小的一个，包含6。所以，7-4+1=4。
示例
让我们看下面的实现来更好地理解
import heapq
def solve(intervals, queries):
intervals = sorted(intervals)[::-1]
h = []
res = {}
for q in sorted(queries):
while intervals and intervals[-1][0] <= q:
i, j = intervals.pop()
if j >= q:
heapq.heappush(h, [j - i + 1, j])
while h and h[0][1] < q:
heapq.heappop(h)
res[q] = h[0][0] if h else -1
return [res[q] for q in queries]
intervals = [[2,5],[3,5],[4,7],[5,5]]
queries = [3,4,5,6]
print(solve(intervals, queries))输入
[[2,5],[3,5],[4,7],[5,5]], [3,4,5,6]输出结果
[3, 3, 1, 4]