贪心（leetcode）452. 用最少数量的箭引爆气球

大体来说，就是有一堆气球，每个气球有不同的直径，把它们摆放在平面上，那从侧面来看，就是下边图片的形状：

对于每个气球，只给出其直径左右两边的 x 坐标值，其格式为[x1, x2]。现在给出一组坐标对，形如 points = [[10,16],[2,8],[1,6],[7,12]]， 题目要求我们用从 x 轴下方（x=x0）处沿着 y 轴的正方向箭射，如何用最少的箭将气球全部射爆！射爆气球的条件是 x1 <= x0 <= x2。

按照每个气球的左端点从小到大排序，然后从左到右遍历，找到多个气球重合的最小区间，然后射一次箭，一直到遍历结束。

#include
#include
#include
#include

using namespace std;

class Solution {
private:
	// 传入的参数 a 和 b 如果是引用，可以在一定程度上提高运行的速度
    static bool cmp(const vector &a, const vector &b) {
        return a[0] < b[0];
    }
public:
    int findMinArrowShots(vector>& points) {
        int size = points.size();
        if (size <= 1)
            return size;
            
        int count = 1; // 初始化值为1
        sort(points.begin(), points.end(), cmp);
        
        int num_0, num_1;
        int first_max = points[0][0];
        int end_min = points[0][1];
        // 这里避免在循环里多次调用数组，防止过多的IO，原理详见CSAPP
        for (int i = 1; i < size; i++) {
            num_0 = points[i][0];
            num_1 = points[i][1];
            if(num_0 >= first_max && num_0 <= end_min){
                first_max = first_max < num_0 ? num_0 : first_max;
                end_min = end_min > num_1 ? num_1 : end_min;
            }else{
                count++;
                first_max = num_0;
                end_min = num_1;
            }
        }
        return count;
    }
};


int main() {

    // vector> points = {{10,16},{2,8},{1,6},{7,12}};
    // vector> points = {{1,2},{3,4},{5,6},{7,8}};
    vector> points = {{1,2},{2,3},{3,4},{4,5}};
    // vector> points = {{1,2},{1,2}};
    Solution obj;
    int res = obj.findMinArrowShots(points);
    cout <<"result is :" << res << endl;
    system("pause");
    return 0;
}

在看过其他人的题解后，感觉这个方法很复杂。下边是另一种思路，按照右边端点排序：

class Solution {
    public int findMinArrowShots(int[][] points) {
        
        if(points.length < 1) return 0;
        Arrays.sort(points, (a, b) -> (a[1] - b[1]));
        int count = 1;
        int axis = points[0][1];
        
        for(int i = 1; i < points.length; ++i) {
            if(axis < points[i][0]) {
                count++;
                axis = points[i][1];
            }
        }
        
        return count;
    }
}