【题解】区间选点

题目： 区间选点

题意：

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

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

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

输入格式

第一行包含整数 N，表示区间数。

接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。

输出格式

输出一个整数，表示所需的点的最小数量。

数据范围

1 ≤ N ≤ 10^5,
−10^9 ≤ ai ≤ bi ≤ 10^9

输入样例：

3
-1 1
2 4
3 5

输出样例：

2

思路：

• 涉及区间的贪心题目一般都要先排序再逐个对区间进行操作，要么根据左端点排序，要么根据右端点排序，或者双关键字排序。
• 第一步：将每个区间按右端点从小到大排序。
• 第二步：从前向后依次枚举每个区间。如果当前区间中已经包含点（实际意义就是被维护的“右值”覆盖），就直接跳过。否则选择当前区间的右端点，更新所维护的“右值”。
• 这里的“右值”就是指某个点所能延伸到的最右端，在这个范围内的区间都将包含点。

代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N=100010;
#define PII pair<int,int>

PII p[N];
int n;

bool cmp1(PII a,PII b)
{
    return a.second<b.second;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i) cin>>p[i].first>>p[i].second;

    sort(p+1,p+n+1,cmp1);
    
    int res=1,r=p[1].second;
    for(int i=2;i<=n;++i)
    {
        if(r<p[i].first)
        {
            res++;
            r=p[i].second;
        }
    }
    
    cout<<res;
    return 0;
}