【LeetCode刷题笔记-15 452:用最少数量的箭引爆气球】

题目：

今天我作弊了！因为上来思考了一会真的没有什么好的办法，但是看了题解以后又懂了。（这样学习到底有没有效率啊。。）

题解是这样考虑这个问题的：

1.首先，对于每一支箭，都要尽可能的引爆多的气球。那么我们假设所有的气球都是从>0的坐标点开始，如何确保我们能引爆更多的气球呢。只要保证每一支箭都是右边界最靠左的那个位置就行。

我和题解的思路不太相同，我是这么考虑这个问题的。随便画一张气球有重叠部分的图，假如我们的箭从0开始移动，那么为了引爆更多的气球，必然是在最靠左的右边界射出这支箭才行。因为如果超出了这个边界值，那么就需要多的一支箭回来单独引爆这个气球。

贪心的思想我认为就体现在这里：

既然每个气球都需要被引爆，那么在满足引爆 对箭限制最大的那个气球（因为它一定要被引爆，而箭和其它同时被引爆的气球 都可以迁就它，所以满足它是必须的） 的同时，引爆尽可能多其他的气球。

在付出不变的的前提下，获得尽可能多。—引用自评论区用户hlx

于是，我们可以对点进行右边界升序排列，然后就可以每一次都比对找出第一个起点大于射箭位置的气球，并将它的位置放置到右断点即可保证是右边界最靠左的那个位置（因为已经按照右边界升序排列过了）

最后再提一句，如果是贪心思想的话，**同样的道理，也可以找到所有左边界最靠右的那个点做发射点。**因为要在限制最大的条件下找出引爆最大值的话，这样做感觉也是可以的。但我并没有去验证为什么可以，因为实在想不到怎么去证明这两种做法得到的点的个数是一样的。如果有大佬能证明，请在评论区指个路，谢谢！

最后就是算法（C++）附带测试;

#include<iostream>
#include<algorithm>
using namespace std;

class Solution {
public:
    int findMinArrowShots(vector<vector<int > >& points) {
		if (points.empty()) {//如果为空则直接返回 
            return 0;
        }
        sort(points.begin(),points.end(),[](const vector<int>& u,const vector<int>& v){
        	return u[1]<v[1];//按照右边界升序排列 
		});
		
		int ans = 1;//从第一支箭开始计数
		int pos = points[0][1];//第一支发射的箭在第一个气球的右边界（因为是升序排列，所以可以保证是最左边的右边界）
		for(const vector<int>& ballon:points){//使用迭代器访问气球元素 
			if(ballon[0]>pos){//找到第一个左边界超出当前箭射出位置的气球 
				ans++;
				pos = ballon[1]; 
			} 
		}
		return ans;
    }
};

int main()
{
	vector<vector<int > > points = {{10,16},{2,8},{1,6},{7,12}};
	Solution s;
	int ans = s.findMinArrowShots(points);
	cout<<ans;
}