【题解】最大不相交区间数量

题目：最大不相交区间数量

题意：

给定 N 个闭区间 [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。

输出可选取区间的最大数量。

输入格式

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

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

输出格式

输出一个整数，表示可选取区间的最大数量。

数据范围

1 ≤ N ≤ 10⁵,
−10⁹ ≤ ai ≤ bi ≤ 10⁹

输入样例：

3
-1 1
2 4
3 5

输出样例：

2

思路：

• 第一步：将每个区间按右端点从小到大排序。
• 第二步：从前向后依次枚举每个区间。如果当前区间中已经包含点（实际意义就是被维护的“右值”覆盖），就直接跳过。否则选择当前区间的右端点，更新所维护的“右值”。
• 这里的“右值”就是指某个点所能延伸到的最右端，在这个范围内的区间都将包含点。
• 我们会发现和 区间选点 这道题思路是一样，甚至代码也一样，为什么会这样？我们来看这道题的题意，题目要求我们找到最多的互不相交的区间，而 区间选点 这道题则是要求我们找到最少的点来覆盖所有区间，我们在做这两道题时都是维护了一个“右值”，如果某个区间包含了“右值”，说明他被覆盖了，为了保证点的数量最少，我们尽可能的多的让互相覆盖的区间属于一个点，那么点与点之间就相当于两个互不相交的区间，所以当我们在找最少的点来覆盖所有区间时，实际上就找出了最多的互不相交的区间，数量就等于点的数量。

代码

#include<iostream>
#include<algorithm>

using namespace std;

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

int n;
PII p[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=0,ed=-0x3f3f3f3f;
    for(int i=1;i<=n;++i)
    {
        if(p[i].first>ed)
        {
            res++;
            ed=p[i].second;
        }
    }
    
    cout<<res;
    return 0;
}