用最少数量的箭引爆气球

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), [](vector<int>& lhs, vector<int>& rhs) {
            return lhs[1] < rhs[1];
        });

        int res = 1, right = points[0][1];
        for (int i = 1; i < points.size(); i++) {
            if (points[i][0] > right) {
                res++;
                right = points[i][1];
            }
        }
        return res;
    }
};