贪心算法-射击气球_射击气球算法

什么是贪心算法

贪心算法不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优选择。使用贪心策略要注意局部最优与全局最优的关系，选择当前的局部最优并不一定能推导出问题的全局最优。贪心策略解题需要解决以下两个问题:

1、该问题是否适合使用贪心策略求解，也就是该问题是否具有贪心选择性质 。

2、制定贪心策略，以达到问题的最优解或较优解。

要确定一个问题是否适合用贪心算法求解，必须证明每一步所作的贪心选择最终导致问题的整体最优解。证明的大致过程为：首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始，做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解 。

Leetcode452-射击气球

题目描述：

题目链接

解题框架：

解题思路：

1. 先分析整体，为了尽可能射击到更多的气球，故将气球的各个区间尽可能相交。

2. 所以可按照左端点对区间进行排序，然后从左往右扫描最优情况。

3. 由于只用到射击区间的右端点来进行比较，所以我们可以忽略射击区间左端点这个变量。所以我们只需更新右端点的位置即可。

最优情况的整体思路流程图：

解题代码：

解决问题的Solution类(注意sort函数的使用)

main函数测试程序接口