最近在刷算法题时，又遇到了一道非常经典的贪心题目：给定若干闭区间，求最少需要多少个点，使得每个区间至少包含一个点。这道题看似简单，却完美展现了贪心策略的用处。
问题描述
输入：
\(n\) 个闭区间 \([l_i, r_i]\)（\(1 \le i \le n\)）
输出：
最少需要放置多少个点，使得每个区间都至少包含一个点。
例如：
区间：[1,3], [2,5], [4,6]
答案：2（比如在点3和点6处放置）
我的解法：右端点优先，贪心选点
核心思想：
把所有区间按右端点从小到大排序，然后尽可能“晚”地放点——也就是放在当前区间的右端点上。
为什么这样做？
你希望一个点能覆盖尽可能多的后续区间。那么，越靠右放，越容易“错过”后面的区间；而越靠左放，又可能浪费了覆盖能力。
但如果我们在当前未被覆盖的区间中，选择右端点最小的那个，并把点放在它的右端点上，就能保证这个点“刚好”覆盖它，同时最大化对后续区间的潜在覆盖能力。
代码实现（C++）
#include <bits/stdc++.h>
using namespace std;struct Interval {int left, right;
};bool cmp(const Interval& a, const Interval& b) {return a.right < b.right; // 按右端点升序
}int main() {int n;cin >> n;vector<Interval> intervals(n);for (int i = 0; i < n; ++i) {cin >> intervals[i].left >> intervals[i].right;}sort(intervals.begin(), intervals.end(), cmp);int pointCount = 0;int lastPoint = -1; // 上一个放置的点for (int i = 0; i < n; ++i) {// 如果当前点没被覆盖if (lastPoint < intervals[i].left) {lastPoint = intervals[i].right; // 在右端点放新点pointCount++;}}cout << pointCount << endl;return 0;
}
💡 小提示：判断条件只需
lastPoint < left即可。因为lastPoint始终是非递减的（我们总是往右放点），不可能出现lastPoint > right的情况。
为什么贪心是对的？
要证明贪心算法的正确性，通常需要两个关键性质：
- 贪心选择性质（Greedy Choice Property）
存在一个最优解，其中第一个点就放在右端点最小的区间的右端点上。
证明思路：
假设最优解中第一个点 \(p\) 覆盖了第一个区间 \([l_1, r_1]\)，那么 \(p \in [l_1, r_1]\)。
如果我们把 \(p\) 改成 \(r_1\)，会发生什么？
它依然覆盖 \([l_1, r_1]\)；
对于其他被 \(p\) 覆盖的区间 \([l_j, r_j]\)，由于我们按 \(r\) 排序，有 \(r_j \ge r_1\)；
又因为 \(p \ge l_j\) 且 \(p \le r_1\)，所以 \(l_j \le r_1 \le r_j\)，即 \(r_1\) 也在该区间内！
因此，把点移到 \(r_1\) 不会减少覆盖能力，仍是最优解。
- 最优子结构（Optimal Substructure）
一旦我们在 \(r_1\) 放了一个点，所有包含 \(r_1\) 的区间都被覆盖了。剩下的未被覆盖的区间构成一个规模更小的相同问题，可以递归/迭代地用同样策略解决。
复杂度分析
排序：\(O(n \log n)\)
遍历选点：\(O(n)\)
总时间复杂度：\(O(n \log n)\)
空间复杂度：\(O(n)\)（存储区间）
效率非常高，适用于大规模数据。
我对贪心算法的理解
贪心算法常常被初学者误解为“随便选看起来好的”，但实际上，贪心是一种需要严格证明的策略。
它的魅力在于简洁高效——没有回溯、没有状态记忆，一步到位；直觉友好——很多贪心策略符合人类的“局部最优”直觉；适用性强——在区间问题、图论（如最小生成树）、编码（霍夫曼）等领域大放异彩。
比如本题如果按左端点排序，或者在左端点放点，就可能得到次优解。贪心的正确性必须通过数学证明来支撑，而不是靠测试样例“蒙对”。
总结
区间选点问题是一个经典的贪心模型；
关键策略：按右端点排序 + 在右端点放点；
正确性由贪心选择性质和最优子结构共同保证；
时间复杂度 \(O(n \log n)\)，实用且优雅。