用Python编写查找每个查询的最小间隔的程序

假设我们有一组间隔，其中间隔[i]有一个对(left_i,right_i)表示第i个间隔从left_i开始，到right_i结束（包含两个端点）。我们还有另一个名为queries的数组。第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]，因为查询的处理如下-

对于查询=3：包含3的最小间隔[3,5]，所以5-3+1=3。
对于查询=4：包含4的最小间隔[3,5]，所以5-3+1=3。
对于查询=5：包含5的最小间隔[5,5]，所以5-5+1=1。
对于查询=6：包含6的最小间隔[4,7]，所以7-4+1=4。

要解决这个问题，我们将依次执行以下步骤-

间隔: =按相反顺序对列表间隔进行排序
h：=新列表
res：=新地图
对于排序后的查询列表中的每个q，都要执行
- 当间隔不为空且最后一个间隔的结束时间<=q时，执行:
  - (i，j) =间隔的最后一个间隔，并将其删除
  - 如果j>= q，则
  - 将(j-i+1, j)对插入堆h中
- 当h不为空且h中最上面的时间处于q之前时，执行：
  - 从h中删除顶部元素
- 如果h不为空，则res[q] = h中顶部时间的开始时间，否则为-1
返回所有查询中res[q]的列表

例子

让我们看一下下面的实现，以便更好地理解

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))