题目描述

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

再给你一个整数数组 queries。第 j 个查询的答案是满足 left_i <= queries[j] <= right_i 的 长度最小区间 i 的长度。如果不存在这样的区间，那么答案是 -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。

输入：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。

限制

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

算法1

(双指针) $O((n + q) \log n + q \log q)$

1. 将每个区间拆分为两个端点，然后按照端点从小到大排序。端点相同的，左端点优先。
2. 将询问从小到大排序。
3. 维护一个多重集。
4. 对于每个询问，处理所有小于当前询问的端点，以及等于当前询问的左端点。如果是左端点，则在多重集中添加当前区间的长度，如果是右端点，则在多重集中删除一个当前区间的长度。
5. 然后从多重集中取出最小的区间长度。

时间复杂度

• 排序的时间复杂度为 $O(n \log n + q \log q)$。
• 每个区间长度最多插入到多重集一次，从多重集中删除一次。每个询问需要获取到最小的区间长度。
• 故总时间复杂度为 $O((n + q) \log n + q \log q)$。

空间复杂度

• 需要 $O(n + q)$ 的额外空间存储端点数组，多重集和答案等数据结构。

C++ 代码

class Solution {
public:
    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
        const int n = intervals.size(), m = queries.size();
        vector<vector<int>> pos;
        for (int i = 0; i < n; i++) {
            pos.push_back({intervals[i][0], 0, i});
            pos.push_back({intervals[i][1], 1, i});
        }

        sort(pos.begin(), pos.end());

        vector<int> idx(m);
        for (int i = 0; i < m; i++)
            idx[i] = i;

        sort(idx.begin(), idx.end(), [&](int x, int y) {
            return queries[x] < queries[y];
        });

        vector<int> ans(m);
        multiset<int> s;

        for (int i = 0, j = 0; i < m; i++) {

            while (pos[j][0] < queries[idx[i]] ||
            (pos[j][0] == queries[idx[i]] && pos[j][1] == 0)) {
                int len = intervals[pos[j][2]][1] - intervals[pos[j][2]][0] + 1;
                if (pos[j][1] == 0) s.insert(len);
                else s.erase(s.find(len));
                j++;
            }

            if (s.empty()) ans[idx[i]] = -1;
            else ans[idx[i]] = *s.begin();
        }

        return ans;
    }
};

算法2

(离散化，线段树) $O((n + q) \log (n + q))$

1. 将所有端点和询问的点放在一起进行离散化。
2. 构造线段树，区间修改，单点查询最小值。
3. 这里线段树可以只维护下传标记。

时间复杂度

• 离散化的时间复杂度为 $O((n + q) \log (n + q))$。
• 每次更新和询问，都需要 $O(\log (n + q))$ 的时间。
• 故总时间复杂度为 $O((n + q) \log (n + q))$。

空间复杂度

• 需要 $O(n + q)$ 的额外空间存储离散化数组，线段树和答案等数据结构。

C++ 代码

#define N 300010

class Solution {
private:
    int mi[N << 2];

    int get(int x, const vector<int> &p) {
        return lower_bound(p.begin(), p.end(), x) - p.begin() + 1;
    }

    void update(int L, int R, int v, int l, int r, int rt) {
        if (L <= l && r <= R) {
            mi[rt] = min(mi[rt], v);
            return;
        }

        mi[rt << 1] = min(mi[rt << 1], mi[rt]);
        mi[rt << 1 | 1] = min(mi[rt << 1 | 1], mi[rt]);

        int mid = (l + r) >> 1;
        if (L <= mid) update(L, R, v, l, mid, rt << 1);
        if (mid < R) update(L, R, v, mid + 1, r, rt << 1 | 1);
    }

    int query(int p, int l, int r, int rt) {
        if (l == r)
            return mi[rt];

        mi[rt << 1] = min(mi[rt << 1], mi[rt]);
        mi[rt << 1 | 1] = min(mi[rt << 1 | 1], mi[rt]);

        int mid = (l + r) >> 1;
        if (p <= mid) return query(p, l, mid, rt << 1);
        return query(p, mid + 1, r, rt << 1 | 1);
    }

public:
    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
        vector<int> p;
        for (const auto &i : intervals) {
            p.push_back(i[0]);
            p.push_back(i[1]);
        }

        for (int q : queries)
            p.push_back(q);

        sort(p.begin(), p.end());
        p.resize(unique(p.begin(), p.end()) - p.begin());
        const int n = p.size();

        for (int i = 1; i <= (n << 2); i++)
            mi[i] = INT_MAX;

        for (const auto &i : intervals) {
            int l = get(i[0], p), r = get(i[1], p);
            update(l, r, i[1] - i[0] + 1, 1, n, 1);
        }

        const int m = queries.size();
        vector<int> ans(m);
        for (int i = 0; i < m; i++) {
            int q = get(queries[i], p);
            int res = query(q, 1, n, 1);
            ans[i] = (res == INT_MAX ? -1 : res);
        }

        return ans;
    }
};