题目描述

给定N个闭区间[ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。

输出选择的点的最小数量。

位于区间端点上的点也算作区间内。

样例

输入
3
-1 1
2 4
3 5

输出
2

算法1

(贪心)

先将点按照右端点从小到大的顺序排序,如果区间右端点相等，按照左端点从大到小排序
遍历左右坐标，如果当前坐标的左端点比之前右端点r大，表示区间不相交，res++

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;
typedef pair<int,int> PII;

const int N = 1e5+10;

bool cmp(pair<int,int> c, pair<int,int> d){
    return c.second < d.second || c.second == d.second && c.first > d.first;
}

int main()
{
    int n;
    cin>>n;
    vector<PII> a(n);
    for(int i =0 ;i<n;i++){
        int x, y;
        cin>>x>>y;
        a[i] = {x, y};
    }
    sort(a.begin(), a.end(), cmp);
    int res = 0, r = -1e9;
    for(auto i:a) {
        if(i.first > r) {
            res ++ ;
            r = i.second;
        }
    }
    cout<<res<<endl;


    return 0;
}