模板题，可以用贪心解决。

贪心: 贪心算法他期望通过局部最优从而实现全局最优。

对于本题，我们只要：

1. 将区间按照右端点升序排序。
2. 遍历所有区间，若当前区间包含当前选中的点 ( 第一个点选择第一个区间的右端点 ) ，则 continue， 否则选择当前区间的右端点，答案 ans ++。

tips

我们设 ans 为最优解， cnt 为某一个答案。

欲证：ans = cnt，我们一般需要证明 ans <= cnt，再证明 ans >= cnt，此时得出 ans = cnt 。

1. ans <= cnt， 我们可以进行的合理选法有多种，但是不一定是最优解，当我们运气特别好，选的是最优解时 ans = cnt，所以 ans <= cnt。

2. ans >= cnt， 正难则反，我们用反证法，我们假设 ans < cnt，举个反例：所有区间都没有重合，那么当前答案为区间的个数即 ans = cnt，假设不成立，所以 ans >= cnt。

所以 ans = cnt。

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
struct Node
{
    int l;
    int r;
}a[N];
bool cmp(Node a, Node b)
{
    return a.r < b.r;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        int l, r;
        cin >> l >> r;
        a[i].l = l, a[i].r = r;
    }
    sort(a + 1, a + n + 1, cmp);
    int end = -2e9, res = 0;
    for (int i = 1; i <= n; ++ i)
    {
        if (a[i].l > end)
        {
            res++;
            end = a[i].r;
        }
    }
    cout << res << endl;
    return 0;
}