Leetcode|中等|区间贪心|452. 用最少数量的箭引爆气球

1 区间终点贪心

没啥好说的，和无重叠区间一样，只是依据条件，相切的那个点也算，总之很简单啦

代码语言：javascript复制

class Solution {
private:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    }
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.empty()) return 0;
        sort(points.begin(), points.end(), cmp);
        int count = points.size();
        int end = points[0][1];
        for (int i = 1; i < points.size(); i  ) {
            // 和无重叠区间问题的唯一区别是“<=”而不是“<”
            if (points[i][0] <= end) 
                count--;
            else end = points[i][1];
        }
        return count;
    }
};

leetcode

0 人点赞