Greedy Summary

背包相关问题

乘船问题： 有 $n$ 个人, 重量为 $w_i$, 每艘船最大承重为 $C$, 且最多只能乘坐两个人, 问最多能承载多少人.
思路： 对于第 $i$ 个人来说, 贪能和他一起坐船中最重的 $j$.
证明：
case1. $i$ 自己坐船, 那么加上 $j$,总船数不会增加,但是所能承载的人变多.
case 2. $i$ 与 $k$ 坐在一起,那么把j换过来,得到的新解不会更差.

区间相关问题

选择不相交区间

区间选点问题

区间覆盖问题

huffman Tree

leetcode