刷题笔记一: 贪心算法

用这种发帖的方式来激励自己做总结，从而更好的掌握知识点。题目都是来自leetcode, 如果有啥没概括到的，或者写错的地方，还请大佬们指正！

核心：采用贪心的策略，保证每次操作都是局部最优解，从而使最后得到的结果也是全局最优解。

涉及问题：
1. 分配问题
    1）lc 455: assign cookies。
    策略： 首先把饼干和孩子分别排序，然后考虑饥饿度最小的孩子，刚好给这个孩子喂饱之后转移到喂下一个饥饿度的孩子，直到没有满足条件的饼干存在。
    2） lc 135: candy
    策略：首先把所有孩子的糖果数初始化为1，然后先从左往右遍历，如果右边孩子的评分比左边高，那么右边的孩子的糖果数更新为左边孩子的糖果数+1。同样的道理，再从右往左遍历一次，如果左边的孩子的评分比右边高，则更新左边的孩子的糖果数为右边孩子的糖果数+1. 这样遍历两遍就结束了。

2.区间问题
   1）lc 435: non-overlapping intervals
   策略：在选择保留区间时，区间的结尾很重要‼️。 选择区间结尾越小，余留给其它区间的空间则越大。因此，我们要优先保留结尾小且不相交的区间。具体实现方法：先把区间按照结尾的大小排序，遍历整个区间，每次都用区间的开始值跟前一个被选中的区间（意味着跟上上一个区间没有重叠区间）的结尾值做比较，若没有overlapping,则可被选中。注意：前一个被选中的区间会一直更新，所以比较的值也会一直更新。

练习题：
基础：605, 452, 763, 122.
进阶： 406, 665.