首页 algorithm 杂杂的算法知识

# 区间选点

相当于问最少有多少重叠区间的集合，根据观察我们可以根据下一个区间左端点和上一个区间右端点的比较，判断是否有重叠，为了更好的比较就需要排序，那么就有两种解决方法：按右端点排序 / 按左端点排序

按右端点排序：

  1. 因为是按右端点排序的，所以在 ed >= e[i].l 的情况下， ed <= e[i].r 是一定的，所以不需要特殊判断
  2. ed = e[i].r 需要放在判断条件的里面，因为这个公共点不在新扩展的那部分区域；如果放在判断条件外面，就相当于默认那段新展开的区域也是有选择的点的，但是那一段新展开的区域显然不是和前面的区间的公共段，所以那个选择的公共点不在新展开的区域
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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct edges
{
    int l, r;
    bool operator<(const edges& W)const
    {
        return r < W.r;
    }
}e[N];
int n;
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> e[i].l >> e[i].r;
    sort(e, e + n);
    int res = 0, ed = -2e9;
    for(int i = 0; i < n; i++)
    {
        if(ed < e[i].l) 
        {
            res++;
            ed = e[i].r;
        }
    }
    cout << res;
    return 0;
}

按左端点排序：

  1. 在 ed >= e[i].l 情况下，需要更新公共点所在区间
  2. 在 ed < e[i].l 情况下，证明当前区域和之前的区域没有重叠区间，集合数加 1，更新区间边界
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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct edges
{
    int l, r;
    bool operator<(const edges& W)const 
    {
        return l < W.l;
    }
}e[N];
int n;
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> e[i].l >> e[i].r;
    sort(e, e + n);
    int res = 1, ed = e[0].r;
    for(int i = 1; i < n; i++)
    {
        if(ed >= e[i].l)
        {
            ed = min(ed, e[i].r);
        }
        else
        {
            res++;
            ed = e[i].r;
        }
    }
    cout << res;
    return 0;
}

# 最大不相交区间的数量

  1. 按照前一题区间选点的方式，将所有区间分成几个集合，每个集合中的各个区间都有公共区域。
  2. 若要选择不相交的区域，不相交的区域一定在不同的集合里，所以总集合数就是最大不相交的区域，即区间选点的数量
  3. 和区间选点代码相同

# 区间分组

引入小根堆，对区间右端点进行操作比较，如果当前区间的左端点大于最小的区间右端点，可以直接加入到已有的组；否则，新开一个组。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct edges
{
    int l, r;
    bool operator<(const edges& W)const
    {
        return l < W.l;
    }
}e[N];
int n;
priority_queue<int, vector<int>, greater<int>> q;
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> e[i].l >> e[i].r;
    sort(e, e + n);
    for(int i = 0; i < n; i++)
    {
        if(q.empty() || q.top() >= e[i].l)   q.push(e[i].r);
        else 
        {
            q.pop();
            q.push(e[i].r);
        }
    }
    cout << q.size();
    return 0;
}

# 区间覆盖

  1. 按照区间左端点进行排序，在包含 start 点的所有区间中找到右端点最大的区间

  2. 判断条件

    1. 如果左端点小于 start，就将它的右端点和当前最大右端点进行比较

    2. 得到的最大右端点如果仍小于 start，说明没有包含 start 的区间，break，res = -1

    3. 得到的最大右端点如果大于 end，那么表示整个区间都被表示了，可以退出

    4. 注意：\color{red}{注意：} 因为可能存在

      1 5

      2

      -1 2

      2 4

      这种情况，即待表示的区间右端点 5 大于目前拥有的区间的最大右端点，所以需要再大于 end 的情况下加一个判断，表示走到了结尾

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct edges
{
    int l, r;
    bool operator<(const edges&W)const
    {
        return l < W.l;
    }
}e[N];
int n, s, t, res;
int main()
{
    cin >> s >> t;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> e[i].l >> e[i].r;
    sort(e, e + n);
    bool success = false;
    for(int i = 0; i < n; i++)
    {
        int j = i, st= -2e9;
        while(j < n && e[j].l <= s)
        {
            st = max(st, e[j].r);
            j++;
        }
        if(st < s) 
        {
            res = -1;
            break;
        }
        res++;
        if(st >= t) 
        {
            success = true;
            break;
        }
        s = st;
        i = j - 1;
    }
    if(!success) res = -1;
    cout << res;
    return 0;
}