# 最多不相交区间
给定数轴上的 $N$ 个区间 $[l_i, r_i]$，你需要选择若干个区间，并且这些区间互不相交（两个区间在端点处重合算作相交）。
你最多能选出多少个区间？
## 贪心策略
错误的贪心策略：按左端点排序，每次尽可能选不相交的区间。
正确的贪心策略：对所有区间按右端点 $r_i$ 排序，**每次选右端点最小的、且与已选区间集合不相交的区间**。
- 前一个已选区间的右端点小于当前区间的做端点，即满足 $r_{\text{前}}\lt l_{\text{后}}$，就选择当前区间。
## 通俗理解
可以把它想成“**尽量早腾出时间**”，这样后面才有更多机会塞进更多区间。
### 直觉一句话
要想选得多，就别“占着不走”。**每次选结束最早的那个区间**，能最快把时间轴空出来，给后面留出最大空间。
### 为什么“结束最早”最划算
假设现在你已经决定要选一个“下一段区间”，它必须从当前时刻之后开始。你面前有很多候选：
- 选一个结束很晚的：你会被它“占住”很久，很多本来能选的短区间都会被挡掉。
- 选一个结束最早的：你很快就自由了，之后可选的区间集合只会更多，不会更少。
所以结束越早，越像“**占用更少资源（时间）**”，自然越容易装下更多区间。
### 一个很形象的比喻
把区间看成会议室的预约：
- 你想安排尽量多场不重叠的会议。
- 每次你都应该优先安排**最早结束**的会议，因为它最早释放会议室，后面能安排的场次最多。
这和酒店房间题的核心直觉是同一类：资源紧张时，“先释放资源”通常是最优策略。
### 小例子感受一下
候选区间（按结束时间）：
- $[1,10]$
- $[2,3]$
- $[4,5]$
- $[6,7]$
- $[8,9]$
如果你先选 $[1,10]$，后面一个都选不了，只能选 $1$ 个。
如果你先选结束最早的 $[2,3]$，还能接着选 $[4,5],[6,7],[8,9]$，总共 $4$ 个。
“结束早”让你不会把整段时间一口气堵死。
### 总结
- 你想要“数量最大”，本质是“给未来留最大的选择空间”。
- **选择结束最早的区间**，对未来限制最小（最不挡路）。
- 因此不断重复“选最早结束且不冲突的”，最终就能选到最多。
## 证明
使用 #上下界证明法 进行证明。
令贪心选出的区间数量为 $m$，最优答案为 $\mathrm{ans}$。
### 下界：$\mathrm{ans} \ge m$
贪心算法选出的 $m$ 个区间两两不相交，是一个合法解，因此最优解至少是它，即
$
\mathrm{ans} \ge m
$
### 上界：$\mathrm{ans} \le m$
结合使用 #归纳法 和 #反证法 进行证明。
#### 想法
想办法证明 $\mathrm{ans}$ 不可能 $\ge m + 1$。
令贪心策略中按顺序选出的区间编号依次为 $g_1, g_2, \dots, g_m$，他们的右端点为
$
e_1 \lt e_2 \lt \dots \lt e_m
$
令 $e_0 = -\infty$。贪心策略可以描述为：在所有满足 $l_i \gt e_{k - 1}$ 的候选区间中选取右端点 $r_i$ 最小的区间作为 $g_k$。
右端点最小似乎意味着对于任意选取 $k$ 个区间（$1 \le k \le m$）的方案中，$e_1, e_2, \dots, e_k$ 分别是第 $1, 2, \dots, k$ 个区间中最小的。如果能证明这一点，意味着 $e_m$ 是最小的。
进一步，如果存在选取 $m + 1$ 个区间的方案，那么第 $m + 1$ 个区间的左端点 $\gt e_m$，我们在贪心的执行过程中是能找到此区间，而现在没找到，矛盾，因此反证法证明不存在选取 $m + 1$ 个区间的方案。
接下来我们证明 “$e_k$ 的最小性”。
#### 归纳法
结论：在任何可行方案中，若选了 $k$（$1 \le k \le m$） 个区间，其第 $k$ 个结束时间 $t_k$ 都满足 $t_k \ge e_k$。
1. $k = 1$ 时，贪心选出的区间 $g_1$ 的右端点 $e_1$ 是所有区间中右端点最小值，因此有 $t_1 \ge e_1$。
2. 假设结论对于 $k - 1$ 成立。考虑任意选择 $k$ 个区间的方案，把它们按时间排序，令第 $k - 1$ 个区间的右端点为 $t_{k - 1}$。
1. 由于归纳法，因此有 $t_{k - 1} \ge e_{k - 1}$。
2. 选取的第 $k$ 个区间的左端点必须要 $\ge t_{k - 1} \ge e_{k - 1}$。它一定属于贪心策略中第 $k$ 个区间的候选集合。
3. 由于贪心是在候选集合中选取右端点最小的，因此 $t_k \ge e_k$。
#### 反证法
假设存在方案能选出 $m+1$ 个区间。把它们按时间顺序排列，设第 $m$ 个结束时间为 $t_m$。由归纳法（取 $k=m$）有 $t_m \ge e_m$。第 $m + 1$ 个区间的左端点必须 $\ge t_m \ge e_m$，说明在 $e_m$ 之后仍然存在可选区间，与贪心未找到相矛盾。因此不存在选出 $m + 1$ 个区间的方案，即 $\mathrm{ans} \le m$。
### 结论
由于 $\mathrm{ans} \le m$ 并且 $\mathrm{ans} \ge m$，因此 $\mathrm{ans} = m$。
## 等价问题
给定数轴上的 $N$ 个区间 $[l_i, r_i]$，你需要选择若干个点，使得每个区间内都至少包含一个选定的点（选择的点落在区间的端点也算包含）。