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

pythonserver side programmingprogramming更新于 2025/12/14 8:12:17

假设我们有一个间隔列表，其中 intervals[i] 有一对 (left_i, right_i)，表示从 left_i 开始到 right_i 结束(包括两者)的第 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。
对于 query = 4:区间 [3,5] 是最小的区间，包含 4。因此，5 - 3 + 1 = 3。
对于 query = 5:区间 [5,5] 是最小的区间，包含 5。因此，5 - 5 + 1 = 1.
对于查询 = 6:区间 [4,7] 是最小的区间，包含 6。因此，7 - 4 + 1 = 4。

为了解决这个问题，我们将遵循以下步骤 −

intervals := 按相反顺序对列表区间进行排序
h := 一个新列表
res := 一个新映射
对于查询排序列表中的每个 q，执行
- 当区间不为空且最后一个区间的结束时间 <= q 时，执行
  - (i, j) := 区间中的最后一个区间，并将其删除
  - 如果j >= q，则
    - 将对 (j-i+1, j) 插入堆 h
- 当 h 不为空且 h 中最顶部间隔的结束时间 < q 时，执行
  - 从 h 中删除顶部元素
- 如果 h 不为空，则 res[q] := h 中最顶部间隔的开始时间，否则为 -1
返回查询中所有 q 的 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))