LeetCode 第34天 | 860. 柠檬水找零 406. 根据身高重建队列 452. 用最少数量的箭引爆气球-模拟找零钱的过程。

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;
        sort(points.begin(), points.end(), cmp);
        // 有零用例的情况已经排除，接下来至少需要用一支箭
        int res = 1;
        for (int i = 1; i<points.size(); i++) {
            // 左边界大于上一个右边界，肯定要加一次射箭
            if (points[i][0] > points[i-1][1])
                res++;
            // 否则重叠，更新右边界为重叠部分较短的右边界
            else {
                points[i][1] = min(points[i][1], points[i-1][1]);
            }
        }
        return res;
    }
};