原理
通过证明局部最优解可以得出全局最优解，从而 \(O(n)\) 解决问题。
常用数学归纳法证明贪心正确性。
模板
取 \(x，y\)，计算\(f(x \text{先于} y),f(y \text{先于} x)\)，令\(f(x \text{先于} y)>f(y \text{先于} x)\) ，解出贪心公式。
区间类
区间覆盖
选取尽量少的区间使得区间[s,t]被覆盖
贪心策略：按左端点排序，每次选取左端点被覆盖的、右端点最长的区间
区间选点
选取尽量少的点，使得每个区间都至少有k个点
贪心策略：按右端点排序，每次选取未选区间中右端点最小的区间的最靠右的k-now个点（now为该区间已选点数)
活动安排
选取尽量多的活动，这些活动时间段不重合
贪心策略：按右端点排序，选取右端点最小的一个，把和它重合的区间删掉
调度安排类
乘数和类
给一个序列\(\{w_i\}\)，求 \(\sum^n_{i=1}w_iw_{i+1}\) 最大的排列方案
贪心策略
大数跟大数乘
从大到小排序即可