type
status
date
slug
summary
tags
category
icon
password
Last edited time
Jun 2, 2024 09:07 AM
区间问题，排序不等式
习题：
每次取当前的最优解，最终得到全局最优解
据贪心策略，对要处理的数据先排序(或优先队列)，排序之后的数据就是贪心选择策略。
例1: Dijkstra的求解
例2: 455. 分发饼干
对胃口值和饼干进行从小到大的排序，优先满足胃口值小的孩子，对每个孩子都按顺序地给他分配恰好大于等于其胃口值的饼干
例3: 435. 无重叠区间
对每个区间按右端点排序，因为右端点越小，重叠的可能越低
需要删除的区间个数=全体区间个数-最大不相交区间个数
- 作者:ziuch
- 链接:https://ziuch.com/article/Greed
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。