贪心策略Greedy
每一步按当前规则选择局部最优决策。
- 核心约束
- 是否全局正确需要具体问题的性质或证明。
- 适用问题
- 可证明局部选择性质的优化，或有明确边界的启发式。
- 边界与取舍
- 局部最优不自动保证全局最优。
时间与空间#
n 为候选数；具体成本由排序、优先队列和可行性判断决定。
- 时间成本
- 无统一界；区间调度为 排序 + 选择
- 空间成本
- 区间调度扫描可 ，排序辅助空间依实现
每次局部选择必须有交换论证或其他正确性证明。不能把一个问题上的贪心结论套到另一个目标；按结束时间选最多区间不等同于最大权重区间选择。
基础原理参考资料
MIT 6.046 · Interval Scheduling具体贪心选择、证明思路和不同调度目标的区别。