贪心
贪心在每一步选择当前最有利的候选，并且不回退。使用它需要证明局部选择可以扩展成全局最优解；“看起来最划算”不足以构成正确性依据。
1. 面试核心
先记住这几条，再读正文- 先明确优化目标，再证明当前选择不会降低最优答案。
- 交换论证通过替换某个最优解的首个选择说明安全性。
- 相似题面改变权重或约束后，原有贪心规则可能失效。
2. 区间选择与交换论证
问题：从若干区间中选出最多的互不重叠区间。约定使用 [start,end)，首尾相接可以同时选择。按结束时间升序排序，每次选择与已选区间不冲突的最早结束区间。
假设最优解的第一个区间是 B，贪心选择 A。A 的结束时间不晚于 B，把 B 换成 A 不会压缩后续可用时间，因此仍可保留剩余区间。之后对剩余问题重复同样推理，就能证明最优性。
3. 最小实现
static int maxIntervals(int[][] intervals) {
java.util.Arrays.sort(intervals,
(a, b) -> Integer.compare(a[1], b[1]));
long end = Long.MIN_VALUE;
int count = 0;
for (int[] interval : intervals) {
if (interval[0] >= end) {
count++;
end = interval[1];
}
}
return count;
}
输入要求每项恰有起止两个值且 start 小于 end。[[1,3],[2,4],[3,5]] 得到 2。排序 O(n log n)，扫描 O(n)；该实现会调整输入数组顺序，排序辅助空间由库实现决定。
4. 使用边界
若目标改成区间收益最大，最早结束可能选中低收益短区间，错过一个高收益长区间，此时原来的交换证明不再成立，通常需要加权区间动态规划。
硬币面额为 1、3、4，凑 6 时先取最大面额得到 4+1+1，共三枚；3+3 只需两枚。这个反例说明“每次选最大”不能无条件用于最少硬币问题。练习时先主动寻找能推翻规则的小输入，再讨论实现。
5 · 面试题卡片
先想答案，再翻面题目来自公开面经。点任意一张进入翻卡，可左右切换，看完回到这里。
逐张翻看 1 张 →5.1 怎样判断一个局部最优规则能否用于贪心算法？
出现公司：暂无已核验的公开来源（本站自测）
考察重点：局部选择的安全性、交换论证和反例验证各自的作用。
参考回答
先定义全局目标，再尝试证明：任意最优解都能替换成包含当前选择的解，且目标不变差、后续仍是同类问题。如果找不到这种安全性理由，就构造小规模反例并与穷举最优值比较。测试可以推翻错误规则，但不能代替对全部输入的证明。