包含每个查询的最小区间

标签: 数组 二分查找 排序 扫描线 堆（优先队列）

难度: Hard

给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示第 i 个区间开始于 lefti 、结束于 righti（包含两侧取值，闭区间）。区间的 长度 定义为区间中包含的整数数目，更正式地表达是 righti - lefti + 1 。

再给你一个整数数组 queries 。第 j 个查询的答案是满足 lefti <= queries[j] <= righti 的 长度最小区间 i 的长度 。如果不存在这样的区间，那么答案是 -1 。

以数组形式返回对应查询的所有答案。

示例 1：

输入：intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
输出：[3,3,1,4]
解释：查询处理如下：
- Query = 2 ：区间 [2,4] 是包含 2 的最小区间，答案为 4 - 2 + 1 = 3 。
- Query = 3 ：区间 [2,4] 是包含 3 的最小区间，答案为 4 - 2 + 1 = 3 。
- Query = 4 ：区间 [4,4] 是包含 4 的最小区间，答案为 4 - 4 + 1 = 1 。
- Query = 5 ：区间 [3,6] 是包含 5 的最小区间，答案为 6 - 3 + 1 = 4 。

示例 2：

输入：intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
输出：[2,-1,4,6]
解释：查询处理如下：
- Query = 2 ：区间 [2,3] 是包含 2 的最小区间，答案为 3 - 2 + 1 = 2 。
- Query = 19：不存在包含 19 的区间，答案为 -1 。
- Query = 5 ：区间 [2,5] 是包含 5 的最小区间，答案为 5 - 2 + 1 = 4 。
- Query = 22：区间 [20,25] 是包含 22 的最小区间，答案为 25 - 20 + 1 = 6 。

提示：

  • 1 <= intervals.length <= 105
  • 1 <= queries.length <= 105
  • intervals[i].length == 2
  • 1 <= lefti <= righti <= 107
  • 1 <= queries[j] <= 107

Submission

运行时间: 291 ms

内存: 50.9 MB

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        qindex = list(range(len(queries)))
        qindex.sort(key=lambda i: queries[i])
        intervals.sort(key=lambda i: i[0])
        pq = []
        res = [-1] * len(queries)
        i = 0
        for qi in qindex:
            while i < len(intervals) and intervals[i][0] <= queries[qi]:
                heappush(pq, (intervals[i][1] - intervals[i][0] + 1, intervals[i][0], intervals[i][1]))
                i += 1
            while pq and pq[0][2] < queries[qi]:
                heappop(pq)
            if pq:
                res[qi] = pq[0][0]
        return res

Explain

此题解采用排序和优先队列（堆）的方法来解决问题。首先，对查询按值进行排序，并保留原始索引以便最后能正确地放置答案。接着，对区间按起始位置进行排序。对于每个查询，使用最小堆来维护所有包含当前查询点的区间，并确保堆中区间的结束位置至少大于等于查询值。堆中存储元组，包含区间长度、起始位置和结束位置，按长度排序以快速获得最小长度的区间。对于每个查询，将所有起始位置小于等于查询值的区间加入堆中，然后移除堆中所有结束位置小于查询值的区间。如果堆非空，堆顶元素即为包含该查询值的最小区间长度。

时间复杂度: O((n+m) log n)

空间复杂度: O(n + m)

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        qindex = list(range(len(queries)))  # 创建查询的索引列表
        qindex.sort(key=lambda i: queries[i])  # 根据查询值对索引排序
        intervals.sort(key=lambda i: i[0])  # 根据区间起始位置排序
        pq = []  # 初始化一个最小堆
        res = [-1] * len(queries)  # 初始化结果数组，全部设为-1
        i = 0  # 区间列表的指针
        for qi in qindex:  # 遍历排序后的查询索引
            while i < len(intervals) and intervals[i][0] <= queries[qi]:  # 将所有起始位置<=当前查询的区间加入堆
                heappush(pq, (intervals[i][1] - intervals[i][0] + 1, intervals[i][0], intervals[i][1]))  # 堆中加入区间长度和区间边界
                i += 1  # 移动区间指针
            while pq and pq[0][2] < queries[qi]:  # 从堆中移除所有结束位置<当前查询的区间
                heappop(pq)  # 弹出堆顶元素
            if pq:  # 如果堆非空
                res[qi] = pq[0][0]  # 取堆顶元素的区间长度作为答案
        return res  # 返回结果数组

Explore

对查询值进行排序是为了按顺序处理每个查询点，从而有效地管理堆（优先队列）。这种排序使得在逐渐增加查询值的过程中，只需要向堆中添加新区间，而不需要重复检查之前已经不满足条件的区间。对区间按起始位置排序是为了便于将所有起始位置小于等于当前查询值的区间顺序加入堆中。这种排序方式减少了对区间集合的重复遍历，提高算法效率，从而实现线性时间的遍历而不是每次查询都进行全量的区间检查。

在本题中，目标是找到包含查询点的最小区间。因此，使用最小堆按区间长度进行排序可以直接获得当前查询点所在的最小区间。如果按照结束位置或开始位置排序，虽然可以管理区间的范围，但无法直接得到最小长度的区间，从而无法直接响应题目的需求。通过按长度排序，每次堆顶的区间即为满足条件的最短区间，这样可以在O(1)时间内直接获得答案，大大提升查询效率。

移除所有结束位置小于当前查询值的区间可能导致堆操作变多，因为每个查询都可能需要从堆中移除多个不满足条件的区间。这些操作包括多次弹出堆顶元素，直到找到一个有效的区间，每次弹出操作都是对数时间复杂度。这可能在区间和查询非常密集的情况下影响总体性能。一种更有效的策略可能是使用延迟删除，即不立即从堆中删除过期区间，而是在堆顶元素需要被使用时检查其有效性，如果无效再进行删除。这样可以减少不必要的删除操作，只在必要时才进行堆调整。