贪心
贪心每步保留一个局部选择，并据此缩小问题。本文负责区间选择、交换证明与权重边界。
1. 面试核心
先记住这几条，再读正文- 正确性证明。 贪心的每次选择都需保留至少一个全局最优解。可用交换论证说明：把最优解的一步替换为当前选择，仍可行且目标值不变。卡 · 区间选择与交换论证
- 无权区间调度。 无权区间调度按结束时间升序选择，能为后续留下尽早开始的空间，从而得到最多兼容区间。
- 带权问题。 区间改为不同收益后，最早结束规则失去最优保证。较早结束的低收益区间可能挤掉高收益区间，需要比较选与不选的总收益。卡 · 权重与目标变化
2. 区间选择与交换论证
目标是选出最多的互不重叠区间。区间使用 [start,end)，且 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. 权重与目标变化
给 A=[0,2) 收益 1，B=[2,4) 收益 1。再给 C=[0,4) 收益 100。最早结束会选 A+B，收益只有 2。若目标为最大收益，应选择 C。
原交换论证仅保留区间数量，并未保留收益。加权问题可按结束时间排序。令 p(i) 为 i 之前最后一个兼容区间。转移为 dp[i]=max(dp[i-1],weight[i]+dp[p(i)])。
5. 使用边界
面额 1、3、4 凑 6，最大面额优先得到 4+1+1。最优解却是 3+3。因此，任意面额的最少硬币问题需额外证明。
反例能否定一个规则，通过样例则只验证这些输入。交换、领先性或其他完整论证用于证明全部合法输入。
6 · 面试题卡片
本页题目与参考回答
6.1 怎样证明局部选择能用于贪心？
考察重点：交换后可行性与目标保持。
相关内容：区间选择与交换论证。
参考回答
证明至少一个最优解可以改成包含当前选择即可。
替换后需保持可行，目标值也应保持最优。再对剩余同类问题重复证明。小规模穷举可找反例，但测试覆盖有限输入。
6.2 最早结束为何能最大化区间数量，却无法保证收益？
考察重点：优化目标与交换证明边界。
相关内容：权重与目标变化。
参考回答
替换首项能保留数量，却会改变收益。
收益 1 的两个短区间会挤掉收益 100 的长区间。带权问题需要比较选与不选，可用加权区间 DP。