# 1851. 包含每个查询的最小区间 (Hard)

## 问题描述

[1851. 包含每个查询的最小区间] (Hard)

[link]: https://leetcode.cn/problems/minimum-interval-to-include-each-query/

给你一个二维整数数组 `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 == 2`
- `1 <= 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` 对应的最小区间长度了。

## 代码

```cpp
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;
    }
};
```