区间选点

算法笔记

原题链接

思路描述

将所有区间根据区间的右端点进行排序，首先，记录最开始右端点的区间值，遍历后面的区间。如果后面区间的左端点大于等于该值，那么说明可以使用一个点来表示。如果无法表示，那么就说明需要增加一个点来使其再区间的内部。

算法证明

设该算法得到的点数为res，正确答案为ans，下面证明$res == ans$。

  1. 证明$res \geq ans$

    由于该算法肯定是正确的，而ans又是最小值，因此该不等式肯定成立。

  2. 证明$res\leq ans$

​ 在上述算法中，每次新记录一个右端点值的所有区间，实际上就是没有任意交集的区间，它们的个数正好是res。根据题目要求的描述，如果有res个没有交集的区间，那么至少就有res个点，因此有$res\leq ans$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> v;
int n, res, r;
int main() {
    scanf("%d", &n);
    while(n--) {
        int a, b;
        scanf("%d%d", &a, &b);
        v.push_back(make_pair(b, a));
    }
    sort(v.begin(), v.end());
    r = -1000000001;
    for(auto ele : v) {
        int b = ele.first, a = ele.second;
        if(a > r) {
            res++;
            r = b;
        }
    }
    printf("%d", res);
    return 0;
}