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]
解释：查询处理如下：
- 查询 = 2：区间 [2,4] 是包含 2 的最小区间，答案为 4 - 2 + 1 = 3 。
- 查询 = 3：区间 [2,4] 是包含 3 的最小区间，答案为 4 - 2 + 1 = 3 。
- 查询 = 4：区间 [4,4] 是包含 4 的最小区间，答案为 4 - 4 + 1 = 1 。
- 查询 = 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]

提示：

  • 1 <= intervals.length <= 10^5
  • 1 <= queries.length <= 10^5
  • intervals[i].length == 2
  • 1 <= lefti <= righti <= 10^7
  • 1 <= queries[j] <= 10^7

解题思路

这道题的核心思想是使用扫描线算法结合优先队列来高效处理查询。

算法思路：

  1. 排序预处理：将查询按值排序，同时记录原始索引；将区间按左端点排序。

  2. 扫描线策略：按照查询值从小到大处理，这样可以保证当处理查询q时，所有左端点≤ q的区间都已经被考虑过了。

  3. 动态维护有效区间：

    • 使用最小堆维护当前可能包含查询点的区间，堆顶是长度最小的区间
    • 当处理查询q时，先将所有left ≤ q的区间加入堆中
    • 然后移除所有right < q的无效区间（这些区间不包含当前查询点）
    • 堆顶就是包含查询点的最小区间

  4. 时间复杂度优化：通过排序避免了对每个查询都遍历所有区间，将复杂度从O(nm)优化到O((n+m)logn)。

这种方法特别适合处理大量查询的场景，因为我们只需要扫描一次就能处理所有查询。

推荐解法：扫描线 + 优先队列

代码实现

class Solution {
public:
    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
        int n = queries.size();
        vector<pair<int, int>> sortedQueries;
        for (int i = 0; i < n; i++) {
            sortedQueries.push_back({queries[i], i});
        }
        sort(sortedQueries.begin(), sortedQueries.end());
        
        sort(intervals.begin(), intervals.end());
        
        vector<int> result(n, -1);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        int i = 0;
        
        for (auto& query : sortedQueries) {
            int q = query.first;
            int idx = query.second;
            
            while (i < intervals.size() && intervals[i][0] <= q) {
                int left = intervals[i][0], right = intervals[i][1];
                pq.push({right - left + 1, right});
                i++;
            }
            
            while (!pq.empty() && pq.top().second < q) {
                pq.pop();
            }
            
            if (!pq.empty()) {
                result[idx] = pq.top().first;
            }
        }
        
        return result;
    }
};

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        sorted_queries = sorted((q, i) for i, q in enumerate(queries))
        intervals.sort()
        
        result = [-1] * len(queries)
        min_heap = []
        i = 0
        
        for q, idx in sorted_queries:
            while i < len(intervals) and intervals[i][0] <= q:
                left, right = intervals[i]
                heapq.heappush(min_heap, (right - left + 1, right))
                i += 1
            
            while min_heap and min_heap[0][1] < q:
                heapq.heappop(min_heap)
            
            if min_heap:
                result[idx] = min_heap[0][0]
        
        return result

public class Solution {
    public int[] MinInterval(int[][] intervals, int[] queries) {
        var sortedQueries = queries.Select((q, i) => new { Query = q, Index = i })
                                  .OrderBy(x => x.Query)
                                  .ToArray();
        
        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
        
        var result = new int[queries.Length];
        Array.Fill(result, -1);
        
        var pq = new SortedSet<(int length, int right)>();
        int i = 0;
        
        foreach (var item in sortedQueries) {
            int q = item.Query;
            int idx = item.Index;
            
            while (i < intervals.Length && intervals[i][0] <= q) {
                int left = intervals[i][0], right = intervals[i][1];
                pq.Add((right - left + 1, right));
                i++;
            }
            
            while (pq.Count > 0 && pq.Min.right < q) {
                pq.Remove(pq.Min);
            }
            
            if (pq.Count > 0) {
                result[idx] = pq.Min.length;
            }
        }
        
        return result;
    }
}

var minInterval = function(intervals, queries) {
    const sortedQueries = queries.map((q, i) => [q, i]).sort((a, b) => a[0] - b[0]);
    intervals.sort((a, b) => a[0] - b[0]);
    
    const result = new Array(queries.length).fill(-1);
    const minHeap = new MinPriorityQueue({ priority: x => x[0] });
    let i = 0;
    
    for (const [q, idx] of sortedQueries) {
        while (i < intervals.length && intervals[i][0] <= q) {
            const [left, right] = intervals[i];
            minHeap.enqueue([right - left + 1, right]);
            i++;
        }
        
        while (!minHeap.isEmpty() && minHeap.front().element[1] < q) {
            minHeap.dequeue();
        }
        
        if (!minHeap.isEmpty()) {
            result[idx] = minHeap.front().element[0];
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
排序查询和区间O(n log n + m log m)O(m)
扫描线处理O(n log n)O(n)
总体O(n log n + m log m)O(n + m)

其中 n 是区间数量，m 是查询数量。

相关题目