image.png

    实战中多个贪心找最优，基于某种标准做个排序
    image.png
    题目一：会议排期
    image.png
    贪心策略1: 按照开始时间排序，不断选取开始时间短的，不冲突的
    贪心策略2：按照结束时间排序，不断选取结束时间短的，跟前面不冲突的
    tips：贪心策略2在求解重复险段数量的题目上有用到。
    image.png
    贪心策略3: 持续时间短
    image.png
    贪心策略2的实现：
    image.png
    image.png
    image.png
    数学上的暗礁。
    题目二：image.png
    image.png
    题目三： 切金条问题，
    一上来把所有数字扔到小根堆里，每次拿两个数字做结合，不断往上直到达到最终的和
    image.png
    image.pngimage.png
    image.png
    image.png
    tips ：

    • 这里用的小根堆，java中的priorityQueue，
    • 贪心策略：堆和排序是最重要的技巧，
    • 排序改变交换顺序，堆是每次取最小的几个值。

    题目4:
    image.png
    tips：profits是利润，比如花费3，收益1， 收回收益后本金是4；
    解法1 ： （是错误的，跟有道题目弄混了）
    有序表，找到小于自己当前m的，收益最大方式，串行的做k个项目。
    step1 ： 先按照cost进行排序，
    step2: 保证profits是递增序，删除掉花费大，收益小的项目
    step3: 将剩余的项目加入有序表，key为cost， value为收益
    step4: 根据当前的m，在有序表中找到花费小于m的最近的元素，
    step5：更新m，remove掉有序表中做完的元素。
    step6: 如果全部做完还没有到达k，要从已经删除的项目中再进行这个操作。
    解法2: 小根堆，
    step1: 将所有项目组织成对象，按照花费放入小根堆
    step2: 将小根堆中花费小于m的弹出，并按照收益放入大根堆
    step3:从大根堆中弹出一个，计算新的收益m，
    step4:利用新的m阈值在从小根堆中弹出能做的项目，加入大根堆
    step5：重复step3，直到弹出k个项目或者大根堆为空为止。
    tips：贪心最常用的就是排序和大根堆和小根堆。
    image.png
    image.png