数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：查找包含每个查询的最小区间
假设我们有一个区间列表，其中intervals[i]包含一对(left_i, right_i)，表示第i个区间从left_i开始，到right_i结束（均包含）。我们还有一个名为queries的数组。第j个查询的答案是包含queries[j]的最小区间i的大小，即right_i - left_i + 1。如果我们找不到这样的区间，则返回-1。我们必须找到一个包含查询答案的数组。
因此，如果输入类似于intervals = [[2,5],[3,5],[4,7],[5,5]] queries = [3,4,5,6]，则输出将为[3, 3, 1, 4]，因为查询按以下方式处理：
对于查询= 3：区间[3,5]是最小的包含3的区间。所以，5 - 3 + 1 = 3。
对于查询= 4：区间[3,5]是最小的包含4的区间。所以，5 - 3 + 1 = 3。
对于查询= 5：区间[5,5]是最小的包含5的区间。所以，5 - 5 + 1 = 1。
对于查询= 6：区间[4,7]是最小的包含6的区间。所以，7 - 4 + 1 = 4。
为了解决这个问题，我们将遵循以下步骤：
intervals := 将区间列表intervals按降序排序
h := 一个新的列表
res := 一个新的映射
对于排序后的查询列表中的每个q，执行以下操作：
当intervals不为空且最后一个区间的结束时间小于等于q时，执行以下操作：
(i, j) := intervals中的最后一个区间，并将其移除
如果j大于等于q，则
将(j-i+1, j)插入堆h中
当h不为空且h中顶部区间的结束时间小于q时，执行以下操作：
从h中删除顶部元素
如果h不为空，则res[q] := h中顶部区间的起始时间，否则res[q] := -1
返回queries中所有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))输入
[[2,5],[3,5],[4,7],[5,5]], [3,4,5,6]
输出
[3, 3, 1, 4]
301 次浏览
