用最少数量的箭引爆气球
计算交叠区间法（时间复杂度高，但是没超时）
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; } };
