问题
在数轴上给 n 个区间 [aᵢ, bᵢ]，选最少的点，让每个区间至少包含一个点。
贪心策略
排序：按区间右端点从小到大排序
选点：从左到右扫描：
如果当前区间没被上一个点覆盖
就选这个区间的右端点作为新点
c++【
sort(区间, 按右端点排序);
点集合 = [];
上一个点 = -∞;
for(每个区间){
if(区间左端点 > 上一个点){
选区间的右端点作为新点;
加入点集合;
上一个点 = 当前右端点;
}
}
】
为什么是对的？
核心思想：早结束的区间要先照顾，选它的右端点可以尽量覆盖更多后面的区间。
简单证明：
第一个区间必须有点，选它右端点最"划算"：
这是最早结束的区间
选这里可以覆盖所有和它重叠的区间
选完后，去掉已被覆盖的区间，问题变小了，同样方法继续。
时间复杂度
排序：O(n log n) ← 主要开销
扫描：O(n)
总共：O(n log n)
贪心算法要点
贪心选择性质：局部最优能导致全局最优
最优子结构：做完选择后，剩下还是同类问题
特点：简单、高效，但只对特定问题有效