MENU

LeetCode452. 用最少数量的箭引爆气球

July 5, 2018 • Read: 344 • LeetCode

image
说一下思路:

  1. 对各个气球按照气球的做端点从小到大排序
  2. 遍历气球数组,同时维护一个射击区间,在满足可以将当前气球射穿的情况下,尽可能击穿更多气球,每击穿一个新的气球,更新一次射击区间
  3. 如果新的气球没办法击穿了,就需要一个新的弓箭手,即,增加一个新的射击区间,然后继续遍历气球数组
    image
bool cmp(pair<int,int> &a,pair<int,int> &b){
        return a.first < b.first;
}
class Solution {
public:
    int findMinArrowShots(vector<pair<int, int>>& points) {
        if(points.size() == 0)
            return 0;
        sort(points.begin(),points.end(),cmp);//按照左端点从小到大排序
        int shoot_num = 1;
        int shoot_begin = points[0].first;
        int shoot_end = points[0].second;
        for(int i = 1;i < points.size();i++){
            if(points[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;
    }
};
最后编辑于: October 10, 2018
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment