寻找包含 Python 中每个查询的最小间隔的程序

• Z时代
• 2024-01-10
• 分类：综合

假设我们有一个区间列表，其中区间 [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。

• for query = 4：区间 [3,5] 是最小的一个，包含 4。所以，5 - 3 + 1 = 3。

• for query = 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]

以上是 寻找包含 Python 中每个查询的最小间隔的程序 的全部内容， 来源链接： utcz.com/z/352619.html