Leetcode 452. Minimum Number of Arrows to Burst Balloons(python+cpp)

题目

解析

Leetcode官方solution这边对贪心策略有一段话挺经典

这道题目跟435本质上是一样的，只不过435是让你算要去掉多少个气球，而这边是算要用多少支箭，具体流程如下：

• 将intervals按照结尾排序
• 将第一个interval的结尾作为基准，如果下一个interval的start晚于基准，那么count+1，同时基准往后移
• 否则无需操作，因为可以用同一只箭解决，基准仍旧不变

python代码

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0
        points.sort(key = lambda x:x[1])
        count = 1
        prev = points[0][1]
        for i in range(1,len(points)):
            if prev < points[i][0]:
                count+=1
                prev = points[i][1]
        return count
        

C++版本

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.empty()) return 0;
        sort(points.begin(),points.end(),[](vector<int> a, vector<int> b){
            return a[1]<b[1];
        });
        int count = 1,prev = points[0][1];
        for (int i =1;i<points.size();++i){
            if (prev<points[i][0]){
                ++count;
                prev = points[i][1];
            }
        }
        return count;
    }
};