$\color{green}{<–画图不易，点下这里赞一下吧}$

题意解读

数轴上有一些区间，在数轴上选取几个点，要求每个区间上最少有一个点。

题解

可以使用贪心解决。

1. 将区间按右端点排序

2. 遍历区间，如果该区间中不包含最后选的那个点，则选取区间右端点。如果包含最后选的那个点，则跳过。

3. 输出所选点的个数。

证明

假设最优解为 ans 个点，贪心算法求出的为 cnt 个点。 只需要证明 ans == cnt 即可。

因为 ans 是最优解，所以 ans <= cnt。

贪心算法求出的结果为 cnt,每次让选取点数+1的区间一定不相交。共计cnt个这样的区间。，为了覆盖这cnt个区间, 至少需要cnt个点。所以ans >= cnt。

综上： cnt == ans

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N  = 100010;
//保存区间
vector<vector<int>> a(N,vector<int>(2,0));
int n;

int main()
{
    cin >> n;
    //读入区间
    for(int i = 0; i< n; i++)
    {
        int l, r;
        cin >> l >> r;
        a[i][0] = l;
        a[i][1] = r;
    }
    // 按右端点排序
    sort(a.begin(), a.begin() + n, [](vector<int> &a, vector<int> &b){return a[1] < b[1];});
    // res 保存答案，end 是当前选的点
    int res = 0, end = -1e9 - 10;
    // 遍历区间
    for(int i = 0; i < n; i++)
    {
        // 如果当前选的点覆盖了该区间，则跳过
        if(end >= a[i][0] && end <= a[i][1]) 
            continue;
        else
        {
            // 选的点+1, 选的点更新为区间右端点
            res++;
            end = a[i][1];
        }
    }
    cout << res;
    return 0;
}