用最少数量的箭引爆气球

计算交叠区间法（时间复杂度高，但是没超时）

class Solution {
public:
    static bool compare(vector<int> &a , vector<int> &b)
    {
        return a[0] < b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end(),compare); //按照气球的起始位置排序
        int result = 0 ;
        vector<vector<int>> cover;
        for(int i=0 ; i<points.size(); i++)
        {
           if(cover.size()==0) //第一个气球的区间，直接设置为第一个重叠取
           {
               cover.push_back(points[i]);
               continue;
           } 
           
           for(int j=0 ;j<cover.size();j++) //遍历重叠区，看新气球有没有和已有区域重叠的
           {
               if(cover[j][1] >= points[i][0]) //发现新气球和已有区域重叠
               {
               		//部分重叠
                    if(points[i][0] >= cover[j][0] && points[i][1] > cover[j][1]) 
                        cover[j][0] = points[i][0]; //更新重叠区（越更新越小）
                    //新气球是已有重叠区域的子集，更新重叠区
                    else if(points[i][0] >= cover[j][0] && points[i][1] <= cover[j][1]) 
                        cover[j] = points[i];   
                    break;                 
               }
               //不属于任何一个重叠区，自己为一个新区
               if(j == cover.size()-1 )
               {
                   cover.push_back(points[i]);
                   break;
               }
           }
        }
        return cover.size(); //一个重叠区一个箭
    }
};

贪心法

class Solution {
public:
    static bool compare(vector<int> &a , vector<int> &b)
    {
        return a[0] < b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end(),compare);
        int result = 1 ;
       
        for(int i=1 ; i<points.size(); i++)
        {
            if (points[i][0] > points[i - 1][1]) // 气球i和气球i-1不挨着，注意这里不是>=
            {  
                result++; // 需要一支箭
            }
            else // 气球i和气球i-1挨着
            {  
                points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界
            }
        }
        return result;
    }
};

二刷

class Solution {
public:
    static bool cmp(vector<int> &a , vector<int> &b)
    {
        return a[0] <= b[0]; 
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.size()==0) return 0;
        int result = 1;
        sort(points.begin(),points.end(),cmp);

        for(int i=0 ; i<points.size() ;i++)
            cout<<points[i][0]<<' '<<points[i][1]<<endl;

        for(int i=1 ; i<points.size() ;i++)
        {
           if(points[i][0] > points[i-1][1]) result++;
           else points[i][1] = min(points[i][1],points[i-1][1]);
        }
        return result;
    }
};