【题目来源】
AcWing：908. 最大不相交区间数量 - AcWing题库
【题目描述】
给定 \(N\) 个闭区间 \([a_i,b_i]\)，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。
输出可选取区间的最大数量。
【输入】
第一行包含整数 \(N\)，表示区间数。
接下来 \(N\) 行，每行包含两个整数 \(a_i,b_i\)，表示一个区间的两个端点。
【输出】
输出一个整数，表示可选取区间的最大数量。
【输入样例】
3
-1 1
2 4
3 5
【输出样例】
2
【算法标签】
《AcWing 908 最大不相交区间数量》 #贪心#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 100005; // 定义最大区间数量int n; // 区间数量// 定义区间结构体
struct Range
{int l, r; // 区间的左右端点// 重载小于运算符，用于排序bool operator < (const Range &W) const{return r < W.r; // 按照区间的右端点升序排序}
}range[N]; // 定义区间数组int main()
{cin >> n; // 输入区间数量// 输入每个区间的左右端点for (int i=0; i<n; i++){int l, r;cin >> l >> r;range[i] = {l, r}; // 将区间存入数组}sort(range, range+n); // 按照区间的右端点进行排序int res = 0; // 记录最大不相交区间的数量int ed = -2e9; // 记录当前最后一个不相交区间的右端点，初始化为负无穷// 遍历所有区间for (int i=0; i<n; i++)if (range[i].l > ed) // 如果当前区间的左端点大于ed，说明不相交{res++; // 不相交区间数量加1ed = range[i].r; // 更新ed为当前区间的右端点}cout << res << endl; // 输出最大不相交区间的数量return 0;
}
【运行结果】
3
-1 1
2 4
3 5
2