贪心算法是指每一步都求最优解,迭代求得可能是全局最优解的算法。当然局部最优解可能不是全局最优解,也可能是全局最优解,这就要看选择的贪心策略了。一般证明选择的策略是正确的,可以使用数学归纳法来证明,一般证明较难,可以写一个暴力的方式求得最优解,然后试不同的贪心策略,看哪一种正确即可,这个就是对数器的思路。
对数器就是通过大量的测试数据来验证算法是否正确的方式。
对数器核心部件有两个:
题目: 给定每一个会议开始的时间和结束的时间,怎么安排会议要求会
议室进行的会议的场次最多。返回这个最多的会议场次。
贪心策略:根据哪个项目早结束安排哪个
代码:
贪心算法,因为是要选一种局部最优解,要么选最大值,要么选最小值。所以基本上贪心算法都可以使用到堆的结构来解决。多做几道贪心算法的题就有感觉了。