04 - 贪心算法¶
1. 核心思想¶
贪心算法在每一步都做当前看起来最优的选择，并期望由局部最优推导全局最优。
适用前提： - 最优子结构 - 贪心选择性质（局部最优可扩展为全局最优）
2. 常见模式¶
- 区间类：按右端点排序选最多不重叠区间
- 资源分配类：按代价/收益排序
- 覆盖类：每次扩展最远可达范围
3. 模板¶
Python
from typing import List, Tuple
def max_non_overlap(intervals: List[Tuple[int, int]]) -> int:
intervals.sort(key=lambda x: x[1])
ans = 0
end = -10**18
for l, r in intervals:
if l >= end:
ans += 1
end = r
return ans
4. 复杂度要求¶
- 排序主导：
O(n log n) - 线性扫描：
O(n) - 组合后通常：
O(n log n)
5. 训练清单¶
- 活动选择 / 区间调度
- 跳跃游戏 I/II
- 分发饼干
- 最少箭引爆气球