包含每个查询的最小区间

发表于 更新于 分类于

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

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

    再给你一个整数数组 queries 。第 j 个查询的答案是满足 lefti <= queries[j] <= righti 的 长度最小区间 i 的长度 。如果不存在这样的区间，那么答案是 -1 。

    以数组形式返回对应查询的所有答案。

    示例 1：

    ```txt

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

    ```txt

    输入：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^5

    • 1 <= queries.length <= 10^5

    • queries[i].length == 2

    • 1 <= lefti <= righti <= 10^7

    • 1 <= queries[j] <= 10^7

题目

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

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

再给你一个整数数组 queries 。第 j 个查询的答案是满足 lefti <= queries[j] <= righti 的 长度最小区间 i 的长度 。如果不存在这样的区间，那么答案是 -1 。

以数组形式返回对应查询的所有答案。

示例 1：

1
2
3
4
5
6
7
输入：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：

1
2
3
4
5
6
7
输入：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^5
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 1 <= lefti <= righti <= 10^7
  • 1 <= queries[j] <= 10^7

题解

方法一：

思路

直接离散化所有出现过的值，不超过3e5个。

区间修改，单点求最小值

线段树模板题，直接使用线段树维护即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Solution {
public:
    using ll = long long;
    #define INF 0x3f3f3f3f
    #define N 300005
    struct Seg{
        int l, r;
        ll val, tag;
    } seg[N<<2];

    void push_up(Seg& u, const Seg& l, const Seg& r) {
        u.val = min(l.val, r.val);
    }

    void push_down(Seg& u, Seg& l, Seg& r) {
        l.val = min(l.val, u.tag);
        l.tag = min(l.tag, u.tag);
        r.val = min(r.val, u.tag);
        r.tag = min(r.tag, u.tag);
        u.tag = INF;
    }

    void seg_build(int id, int l, int r) {
        seg[id].l = l; seg[id].r = r;
        seg[id].val = seg[id].tag = INF;
        if (l == r) {
            return ;
        }
        int m = l+r>>1;
        seg_build(id<<1, l, m);
        seg_build(id<<1|1, m+1, r);
        push_up(seg[id], seg[id<<1], seg[id<<1|1]);
    }

    void seg_update(int id, int l, int r, ll val) {
        if (l <= seg[id].l && seg[id].r <= r) {
            seg[id].val = min(seg[id].val, val);
            seg[id].tag = min(seg[id].tag, val);
            return ;
        }
        push_down(seg[id], seg[id<<1], seg[id<<1|1]);
        int m = seg[id].l + seg[id].r >> 1;
        if (l <= m) seg_update(id<<1, l, r, val);
        if (m < r) seg_update(id<<1|1, l, r, val);
        push_up(seg[id], seg[id<<1], seg[id<<1|1]);
    }

    ll seg_query(int id, int l, int r) {
        if (l <= seg[id].l && seg[id].r <= r) {
            return seg[id].val;
        }
        push_down(seg[id], seg[id<<1], seg[id<<1|1]);
        ll rt = INF;
        int m = seg[id].l + seg[id].r >> 1;
        if (l <= m) rt = min(rt, seg_query(id<<1, l, r));
        if (m < r) rt = min(rt, seg_query(id<<1|1, l, r));
        return rt;
    }

    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& q) {
        int n = intervals.size(), qsz = q.size();
        map<int,int> mp;
        for (int i:q) mp[i];
        for (auto& i:intervals) mp[i[0]], mp[i[1]];
        int sz = 0;
        for (auto& [i,j]:mp) j = ++sz;
        seg_build(1, 1, sz);
        for (auto& i:intervals) {
            seg_update(1, mp[i[0]], mp[i[1]], i[1]-i[0]+1);
        }
        vector<int> rt;
        for (int i:q) {
            rt.push_back((seg_query(1, mp[i], mp[i])+1)%(INF+1)-1);
        }
        return rt;
    }
};

方法二：

思路

动态开点，不用离散化
区间修改，单点查询

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    #define ll long long
    #define INF 0x3f3f3f3f
    struct Node {
        ll l, r, mn, tag;
        Node* ls, *rs;
        Node(ll _l, ll _r):l(_l), r(_r), mn(INF), tag(INF), ls(NULL), rs(NULL) {}
    } *root;

    void push_down(Node* u) {
        ll l = u->l, r = u->r, m = (r-l)/2+l;
        if (u->ls == NULL) {
            u->ls = new Node(l, m);
        }
        if (u->rs == NULL) {
            u->rs = new Node(m+1, r);
        }
        if (u->tag != INF) {
            u->ls->mn = min(u->ls->mn, u->tag);
            u->ls->tag = min(u->ls->tag, u->tag);
            u->rs->mn = min(u->rs->mn, u->tag);
            u->rs->tag = min(u->rs->tag, u->tag);
            u->tag = INF;
        }
    }

    void seg_update(Node* u, ll l, ll r, ll val) {
        if (l <= u->l && u->r <= r) {
            u->mn = min(u->mn, val);
            u->tag = min(u->tag, val);
            return ;
        }
        push_down(u);
        ll m = (u->r-u->l)/2+u->l;
        if (l<=m) seg_update(u->ls, l, r, val);
        if (m<r) seg_update(u->rs, l, r, val);
    }
    ll seg_query(Node* u, ll l, ll r) {
        if (l <= u->l && u->r <= r) {
            return u->mn;
        }
        push_down(u);
        ll rt = INF;
        ll m = (u->r-u->l)/2+u->l;
        if (l<=m) rt = min(rt, seg_query(u->ls, l, r));
        if (m<r) rt = min(rt, seg_query(u->rs, l, r));
        return rt;
    }
    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
        root = new Node(0, 1e9);
        for (auto& i:intervals) {
            seg_update(root, i[0], i[1], i[1]-i[0]+1);
        }
        vector<int> ans;
        for (int i:queries) {
            ans.push_back((seg_query(root, i, i)+1)%(INF+1)-1);
        }
        return ans;
    }
};

方法三：

思路

离线操作，对查询升序排序。

对所有区间左端点升序排序

对于查询位置i，将左端点比i小的区间加入到优先队列中，优先队列优先以区间长度小的排前面。

所以查询点i所处最小区间长度，可以通过优先队列队首得到。

但是由于有失效的区间（队列中右端点小于i的区间）存在，可以采用延迟删除的技巧——不断删除队首右端点小于i的区间。

这样做保证了时间复杂度仍然是$O(nlogn)$,因为每个区间只会进队和出队一次，进队出队时间复杂度$O(logn)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
        sort(intervals.begin(), intervals.end());
        int n = intervals.size(), m = queries.size();
        vector<int> idx(m);
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int a, int b){return queries[a] < queries[b];});
        priority_queue<pair<int,int>> q; // -lenght, right
        int p = 0;
        vector<int> ans(m, -1);
        for (int i:idx) {
            while (p<n && intervals[p][0]<=queries[i]) {
                q.emplace(-(intervals[p][1]-intervals[p][0]+1), intervals[p][1]);
                p++;
            }
            while (q.size() && q.top().second < queries[i]) q.pop();
            if (q.size()) ans[i] = -q.top().first;
        }
        return ans;
    }
};