射击气球

LeetCode 452. Minimum Number of Arrows to Burst Balloons
已知在一个平面上有一定数量的气球，平面可以看作一个坐标系，在平面的x轴的不同位 置安排弓箭手向y轴方向射箭，弓箭可以向y轴走无穷远;给定气球的宽度 xstart ≤ x ≤ xend，问至少需要多少弓箭手，将全部气球打爆?
例如: 四个气球 : [[10,16], [2,8], [1,6], [7,12]]，至少需要2个弓箭手。

贪心规律

1.对于某个气球，至少需要使用1只弓箭将它击穿。 2.在这只气球将其击穿的同时，尽可能击穿其他更多的气球!(贪心!)

算法思路

1.对各个气球进行排序，按照气球的左端点从小到大排序。
2.遍历气球数组，同时维护一个射击区间，在满足可以将当前气球射穿的
情况下，尽可能击穿更多的气球，每击穿一个新的气球，更新一次射 击区间(保证射击区间可以将新气球也击穿)。
3.如果新的气球没办法被击穿了，则需要增加一名弓箭手，即维护一个新 的射击区间(将该气球击穿)，随后继续遍历气球数组。

#include <algorithm>
#include<vector>
bool cmp(const std::pair<int,int> &a,const std::pair<int ,int> &b){
    return a.first < b.first;//无需考虑左端点相同时的排序
class Solution{
public:
    int findMinArrowShots(std::vetor<std::pair<int,int>> &points){
    if(points.size() == 0){
        return 0;
    }
    std::sort(points.begin(),points.end(),cmp);//对气球按照左端点从小到大排序
    int shoot_num = 1;//初始化弓箭手数量为1
    int shoot_begin = points[0].first;//初始化射击区间，即为第一个气球的两端点
    int shoot_end = points[0].second;
    for(int i =1; i< points.size();i++){
        if(point[i].first <shoot_end){
            shoot_begin = points[i].first;
            if(shoot_end > points[i].second){
                shoot_end = points[i].second;
            }
        }
        else{
            shoot_num ++;
            shoot_begin = points[i].first;
            shoot_end = points[i].second;
        }
}
    return shoot_num;
}
}; 
}