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

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

输入格式

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

接下来 N 行，每行包含两个整数 a~i~,b~i~，表示一个区间的两个端点。

输出格式

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

数据范围

1≤N≤105,
−10^9^ ≤ a~i~ ≤ b~i~ ≤-10^9^

输入样例：

3
-1 1
2 4
3 5

输出样例：

2

代码演示（自制）：

#include<bits/stdc++.h>
using namespace std;
const int mxn = 1e5 + 5;
int n;
struct qujian {
    int l, r;
    bool operator<(const qujian& h)const {
        return r < h.r;
    }
}h[mxn];
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> h[i].l >> h[i].r;
    sort(h + 1, h + 1 + n);
    int ans = 1, ed = h[1].r;
    for (int i = 2; i <= n; ++i) {
        if (ed < h[i].l) {
            ++ans;
            ed = h[i].r;
        }
        else {
            ed = min(ed, h[i].r);
        }
    }
    cout << ans << '\n';
    return 0;
}

思路：

• 原本是想按照 L 来排序，但后面试验后得知这样操作会导致大的区间会吞并小的区间，那是上道题 905. 区间选点 的写法，不符合本题题意，本体题意是想找出不相容的区间最多有多少。
• 因此决定用 R 来进行排序，ed 存储当前不重合区间的 R 值，在遍历过程中，不存在后面的 R 比前面的 R 小的情况，因此只用判断此时 ed 与 L 的关系，如果 ed 比下一个区间的 L 小，说明下一个区间与现在的区间没有交集，ans 可以 ++；若比下一个 L 大，则说明区间之间有交集。
• 出现有交集的情况，该怎么进行 ed 的转移：原本我认为有交集的区间可以视为一个更大的区间，但后来发现这么想有失偏颇

比如若给你【0,7】，【3,9】，【8,8】这三个区间

最多可以选择【0,7】【8,8】两个区间

但若将【0,7】【3,9】视为【0,9】进行合并，【8,8】将会被遗漏

• 因此为了保证有更多的不相容区间出现的可能，让 ed 等于 r 值较小的那个