问题描述
[1851. 包含每个查询的最小区间] (Hard)
给你一个二维整数数组 intervals ，其中 intervals[i] = [leftᵢ, rightᵢ] 表示第 i 个区间开始于 le ftᵢ 、结束于 rightᵢ（包含两侧取值， 闭区间）。区间的 长度 定义为区间中包含的整数数目，更
正式地表达是 rightᵢ - leftᵢ + 1 。
再给你一个整数数组 queries 。第 j 个查询的答案是满足 leftᵢ <= queries[j] <= rightᵢ 的 长度最
小区间 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 <= 10⁵1 <= queries.length <= 10⁵intervals[i].length == 21 <= leftᵢ <= rightᵢ <= 10⁷1 <= queries[j] <= 10⁷
解题思路
首先，应该注意到，对 intevals 数组排序对结果不会有任何影响，其次，对 queries 排序也不会对答案产生本质影响，只是改变了答案的顺序罢了，只要把 $query$ 的结果和 $query$ 在原先的 queries 数组的索引对应起来就好了。
为了方便，把 queries 转化为 vector<pair<int, int>> qrs;，first 是要查询的值，second 是这个值在 queries 数组中的索引，然后对 qrs 按 first 从小到大排序。
然后准备遍历 qrs 数组，由于 intervals 已经按照从左端点元素从小到大的顺序排好序了，因此我们比较当前 query 与 intervals[idx][0] 的大小，如果 intervals[idx][0] <= query，就将 intervals 入队（队中元素满足了题目要求的一半条件），并递增 idx，表示这个区间我们已经考虑了，直到 idx >= queries.size() || intervals[idx][0] > query。
接着，我们比较当前 query 与堆顶区间的右端点大小（堆顶是区间长度最小的区间），如果右端点小于 query，将该区间弹出，直到堆为空或者堆顶区间的右端点 >= query。
最后，可以更新 query 对应的最小区间长度了。
代码
class Solution {
public:
vector<int> minInterval(vector<vector<int>> &intervals, vector<int> &queries) {
sort(intervals.begin(), intervals.end());
using pii = pair<int, int>;
vector<pii> qrs;
int m = intervals.size(), n = queries.size();
for (int i = 0; i < n; ++i) {
qrs.emplace_back(queries[i], i);
}
std::sort(qrs.begin(), qrs.end());
vector<int> ans(n, -1);
priority_queue<pii, vector<pii>, greater<pii>> pq; // pair.first => right - left + 1，pair.second => right
int idx = 0;
for (int i = 0; i < n; ++i) {
while (idx < m && intervals[idx][0] <= qrs[i].first) {
pq.push({intervals[idx][1] - intervals[idx][0] + 1, intervals[idx][1]});
++idx;
}
while (!pq.empty() && pq.top().second < qrs[i].first) {
pq.pop();
}
if (!pq.empty()) {
ans[qrs[i].second] = pq.top().first;
}
}
return ans;
}
};