贪心算法

贪心算法在每一步做当前看来最优且不可撤销的选择，期望得到全局最优。它不保证对所有问题正确，必须证明贪心选择性质与最优子结构。

活动选择：最早结束优先

为选择最多个互不重叠活动，按结束时间升序排序；每次选择开始时间不早于上一个所选活动结束时间的活动。最早结束活动留下最多余下时间，可通过交换论证证明最优。

struct Act { int l, r; };
sort(a.begin(), a.end(), [](const Act& x, const Act& y) {
    return x.r < y.r;
});
int last = INT_MIN, cnt = 0;
for (auto x : a)
    if (x.l >= last) ++cnt, last = x.r;

排序主导时间 O(n log n)，扫描 O(n)。

常见模型

• 删数：删去第一个比后继数字大的数字，使更小数字前移；可用单调栈 O(n)。
• 部分背包：按单位价值从高到低装入；可分割性是正确关键。
• 哈夫曼/合并果子：每次合并最小两堆，优先队列实现 O(n log n)。

警惕

硬币面额 {1,3,4} 凑 6 时，优先取 4 得 3 枚，却不如 3+3；0/1 背包也不能按单位价值贪心。先找反例或完成交换论证，再使用贪心。