力扣 452. 用最少数量的箭引爆气球

题目来源：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/

C++题解1： 根据x_end排序，x_start小的在前，这样可以保证如果第 i 个球的x_end大于等于第 j 个球的x_start时，第 j 个球能被射中（因为第j个球的x_end更大）。

注意cmp函数，参数要用引用&，否则会超时（我猜是形参复制导致的超时）。

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        if(a[1] < b[1]) return true;
        else if(a[1] == b[1]) {
            if(a[0] < b[0]) return true;
        }
        return false;
    }
    int findMinArrowShots(vectorint>>& points) {
        sort(points.begin(), points.end(), cmp);
        int len = points.size();
        int res = 1, maxind = points[0][1];
        for(int i = 0; i < len; i++) {
            if(points[i][0] > maxind) {
                maxind = points[i][1];
                res++;
            }
        }
        return res;
    }
};

C++题解2（来源代码随想录）：根据x_start排序，比较每个气球与上一个气球是否相连，不相连则需要一支箭，相连则把尾巴更新为最短的x_end，避免[1,3][2,5][4,6]这样，需要两个箭，因为第一个气球与第三个气球不相连。

class Solution {
private:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
public:
    int findMinArrowShots(vectorint>>& points) {
        if (points.size() == 0) return 0;
        sort(points.begin(), points.end(), cmp);
 
        int result = 1; // points 不为空至少需要一支箭
        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;
    }
};