905 区间选点

905 区间选点

 题意：尽可能少的点，让所有的区间都至少有一个点

贪心题：猜想+证明

 分析：1.让区间按照右端点的大小从小到大排序

            2.如果一个区间没有被放入点，就在他的右端点放一个点，如果这个区间已经被放入点了，则直接pass

也就是两个及以上不完全覆盖的区间，放一个点就可以了

一个区间不需要放两个点使他们和前后区间"串联"

时间复杂度 O(nlogn)
证明
证明ans<=cnt ：cnt 是一种可行方案， ans是可行方案的最优解，也就是最小值。

证明ans>=cnt ： cnt可行方案是一个区间集合，区间从小到大排序，两两之间不相交。

所以覆盖每一个区间至少需要cnt个点。

#include 
#include 
using namespace std;
const int N = 100005;
typedef long long ll;
bool st[N];
struct PII
{
    int l, r;
    bool operator< (const PII b)const
    {
        return r < b.r ? true : false;
    }
}a[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 0;i < n;i++)
        cin >> a[i].l >> a[i].r;
    sort(a, a + n);
    ll res = 0;
    int end = -2e9;
    for (int i = 0;i < n;i++)
        if (a[i].l > end)
        {//当前区间
            res++;
            end = a[i].r;
        }
    cout << res << 'n';
}