题目描述

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

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

输入格式
第一行包含整数$N$，表示区间数。

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

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

数据范围
$1\le N\le 10^5$,
$−10^9\le a_i\le b_i\le 10^9$

输入样例：

3
-1 1
2 4
3 5

输出样例：

2

算法（贪心）

可以参考区间选点那题，二者在算法思路上是一致的

• 将每个区间按照右端点从小到大进行排序
• ed表示当前放置在数轴上的点的位置，开始初始化为无穷小，表示没有放置，此时数轴上没有点
• 依次遍历排序好的区间。如果区间的左端点大于当前放置点的位置，说明当前点无法覆盖区间，则把点的位置更新成该区间的右端点，表示在该区间的右端点放置一个新的点，同时更新点的个数

证明

• 假设$ans$是最优解，表示最多有$ans$个不相交的区间；$cnt$是可行解，表示算法求出$cnt$个不相交的区间，显然有$ans \ge cnt$
• 反证法证明$ans \le cnt$。假设$ans \gt cnt$，由最优解的含义知，最多有$ans$个不相交的区间，因此至少需要$ans$个点才能覆盖所有区间，而根据算法知，只需$cnt$个点就能覆盖全部区间，且$cnt < ans$，这与前边分析至少需要$ans$个点才能覆盖所有区间相矛盾，故$ans \le cnt$
• 综上所述$ans=cnt$

核心代码

struct Range
{
    int l, r;
    bool operator< (const Range &W)const        
    {
        return r < W.r;         // 使sort()按右端点升序排序
    }
}range[N];

// main
sort(range, range + n);         // 按右端点升序排序

int res = 0, ed = -2e9;         // ed为无穷小
for (int i = 0; i < n; i ++ )
    if (ed < range[i].l)
    {
        // 找到一个无法由当前点覆盖的区间
        ed = range[i].r;         // 在数轴上放入新的点
        res ++ ;                // 更新数轴上点的个数
    }

代码实现

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;

struct Range {
    int l, r;
    bool operator< (const Range &x) const {
        return r < x.r;
    }
} range[N];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) 
        scanf("%d%d", &range[i].l, &range[i].r);

    sort(range, range + n);

    int res = 0, ed = -2e9;
    for (int i = 0; i < n; i++)
        if (range[i].l > ed) {
            ed = range[i].r;
            res++;
        }

    cout << res << endl;    

    return 0;
}