1851-包含每个查询的最小区间

给你一个二维整数数组 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

方法一：离线算法 + 优先队列

首先我们对问题进行分析，对于第 j 个查询，可以遍历 intervals，找到满足 left}_i \le \textit{queries}_j \le \textit{right}_i 的长度最小区间 i 的长度。以上思路对于每个查询，都需要重新遍历 intervals。

如果查询是递增的，那么我们可以对 intervals 按左端点 left 从小到大进行排序，使用一个指针 i 记录下一个要访问的区间 intervals}[i]，初始时 i = 0，使用优先队列 pq 保存区间（优先队列的比较 key 为区间的长度，队首元素为长度最小的区间）。对于第 j 个查询，我们执行以下步骤：

如果 i 等于 intervals 的长度或 left}_i \gt \textit{queries}[j]，终止步骤；
将 intervals}[i] 添加到优先队列 pq，将 i 的值加 1，继续执行步骤 1。

此时所有符合 left} \le \textit{queries}_j \le \textit{right 的区间都在 pq，我们不断地获取优先队列 pq 的队首区间：

如果队首区间的右端点 right} \lt \textit{queries}[j]，那么说明该区间不满足条件，从 pq 中出队；
如果队首区间的右端点 right} \ge \textit{queries}[j]，那么该区间为第 j 个查询的最小区间，终止过程。

对于第 j + 1 个查询，因为查询是递增的，所以有 queries}[j + 1] \ge \textit{queries}[j]，那么此时 pq 中的区间都满足 left} \le \textit{queries}[j + 1]。在第 j 个查询中丢弃的区间有 right} \lt \textit{queries}[j] \le \textit{queries}[j + 1]，因此丢弃的区间不满足第 j + 1 个查询。同样在第 j + 1 个查询执行与第 j 个查询类似的步骤，将可能满足条件的区间加入优先队列 pq 中，那么此时所有满足条件的区间都在优先队列 pq 中，执行类似第 j 个查询的出队操作。

由以上分析，如果查询满足递增的条件，那么可以利用优先队列进行优化。题目一次性提供所有的查询，基于离线原理，我们对所有查询从小到大进行排序，然后执行以上算法。

[sol1-C++]class Solution {
public:
    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
        vector<int> qindex(queries.size());
        iota(qindex.begin(), qindex.end(), 0);
        sort(qindex.begin(), qindex.end(), [&](int i, int j) -> bool {
            return queries[i] < queries[j];
        });
        sort(intervals.begin(), intervals.end(), [](const vector<int> &it1, const vector<int> &it2) -> bool {
            return it1[0] < it2[0];
        });
        priority_queue<vector<int>> pq;
        vector<int> res(queries.size(), -1);
        int i = 0;
        for (auto qi : qindex) {
            while (i < intervals.size() && intervals[i][0] <= queries[qi]) {
                int l = intervals[i][1] - intervals[i][0] + 1;
                pq.push({-l, intervals[i][0], intervals[i][1]});
                i++;
            }
            while (!pq.empty() && pq.top()[2] < queries[qi]) {
                pq.pop();
            }
            if (!pq.empty()) {
                res[qi] = -pq.top()[0];
            }
        }
        return res;
    }
};

[sol1-Java]class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        Integer[] qindex = new Integer[queries.length];
        for (int i = 0; i < queries.length; i++) {
            qindex[i] = i;
        }
        Arrays.sort(qindex, (i, j) -> queries[i] - queries[j]);
        Arrays.sort(intervals, (i, j) -> i[0] - j[0]);
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
        int[] res = new int[queries.length];
        Arrays.fill(res, -1);
        int i = 0;
        for (int qi : qindex) {
            while (i < intervals.length && intervals[i][0] <= queries[qi]) {
                pq.offer(new int[]{intervals[i][1] - intervals[i][0] + 1, intervals[i][0], intervals[i][1]});
                i++;
            }
            while (!pq.isEmpty() && pq.peek()[2] < queries[qi]) {
                pq.poll();
            }
            if (!pq.isEmpty()) {
                res[qi] = pq.peek()[0];
            }
        }
        return res;
    }
}

[sol1-C#]public class Solution {
    public int[] MinInterval(int[][] intervals, int[] queries) {
        int[] qindex = new int[queries.Length];
        for (int idx = 0; idx < queries.Length; idx++) {
            qindex[idx] = idx;
        }
        Array.Sort(qindex, (i, j) => queries[i] - queries[j]);
        Array.Sort(intervals, (i, j) => i[0] - j[0]);
        PriorityQueue<int[], int> pq = new PriorityQueue<int[], int>();
        int[] res = new int[queries.Length];
        Array.Fill(res, -1);
        int i = 0;
        foreach (int qi in qindex) {
            while (i < intervals.Length && intervals[i][0] <= queries[qi]) {
                pq.Enqueue(new int[]{intervals[i][1] - intervals[i][0] + 1, intervals[i][0], intervals[i][1]}, intervals[i][1] - intervals[i][0] + 1);
                i++;
            }
            while (pq.Count > 0 && pq.Peek()[2] < queries[qi]) {
                pq.Dequeue();
            }
            if (pq.Count > 0) {
                res[qi] = pq.Peek()[0];
            }
        }
        return res;
    }
}

[sol1-Python3]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

[sol1-Golang]type PriorityQueue [][]int

func (pq PriorityQueue) Len() int {
    return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i][0] < pq[j][0]
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x any) {
    *pq = append(*pq, x.([]int))
}

func (pq *PriorityQueue) Pop() any {
    n, old := len(*pq), *pq
    x := old[n - 1]
    *pq = old[0 : n-1]
    return x
}

func (pq PriorityQueue) Top() []int {
    return pq[0]
}

func minInterval(intervals [][]int, queries []int) []int {
    qindex := make([]int, len(queries))
    for i := 0; i < len(queries); i++ {
        qindex[i] = i
    }
    sort.Slice(qindex, func(i, j int) bool {
        return queries[qindex[i]] < queries[qindex[j]]
    })
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    pq := &PriorityQueue{}
    res, i := make([]int, len(queries)), 0
    for _, qi := range qindex {
        for ; i < len(intervals) && intervals[i][0] <= queries[qi]; i++ {
            heap.Push(pq, []int{intervals[i][1] - intervals[i][0] + 1, intervals[i][0], intervals[i][1]})
        }
        for pq.Len() > 0 && pq.Top()[2] < queries[qi] {
            heap.Pop(pq)
        }
        if pq.Len() > 0 {
            res[qi] = pq.Top()[0]
        } else {
            res[qi] = -1
        }
    }
    return res
}

复杂度分析

时间复杂度：O(m \log m + n \log n)，其中 m 和 n 分别为 intervals 和 queries 的长度。排序需要 O(m \log m + n \log n)，最多执行 m 次入队和出队操作，需要 O(m \log m)。
空间复杂度：O(m + n)。保存 qindex 需要 O(m)，保存 pq 需要 O(n)。