(LeetCode 面试经典 150 题) 452. 用最少数量的箭引爆气球 （排序+贪心）

题目：452. 用最少数量的箭引爆气球

思路：排序+贪心，时间复杂度0(nlogn)。

将数组points按右区间升序排序，要让每个球都被打中，那遍历排序后的数组points即可。细节看注释。

C++版本：

class Solution {
public:
    static bool cmp(vector<int> a,vector<int> b){
        if(a[1]==b[1]) return a[0]<b[0];
        return a[1]<b[1];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
    	// 将数组points按右区间升序排序
        sort(points.begin(),points.end(),cmp);
        int ans=1;
        int r=points[0][1];
        // 遍历排序后的数组points
        for(int i=1;i<points.size();i++){
        	// 当前的弓箭是在r处射出
        	// 如果左区间points[i][0]<=r，那就可以被打中
            if(points[i][0]<=r) continue;
            ans++;
            r=points[i][1];
        }
        return ans;
    }
};

JAVA版本：

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points,new Comparator<int[]>(){
            public int compare(int[] a,int[] b){
                if(a[1]==b[1]) return Integer.compare(a[0],b[0]);
                return Integer.compare(a[1],b[1]);
            }
        });
        int ans=1;
        int r=points[0][1];
        for(int i=1;i<points.length;i++){
            if(points[i][0]<=r) continue;
            ans++;
            r=points[i][1];
        }
        return ans;
    }
}

GO版本：

func findMinArrowShots(points [][]int) int {
    sort.Slice(points,func (i,j int) bool {
        if points[i][1]==points[j][1] {
            return points[i][0]<points[i][1]
        }
        return points[i][1]<points[j][1]
    })
    ans,r:=1,points[0][1]
    for i:=1;i<len(points);i++ {
        if r>=points[i][0] {continue}
        ans++
        r=points[i][1]
    }
    return ans
}