LeetCode 452 Minimum Number of Arrows to Burst Balloons

    
        标签：
        
            贪心法
        
            LeetCode
        
    发布于：2022-02-21 17:09:44
    编辑于：2022-02-21 17:21:58
    浏览量：688

概述

https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/

贪心法

很容易想到，我们应当优先设计重叠区间最多的地方，一个暴力的方法是，先按后端点排序，统计后端点的相交个数，找出最大的后将相关区间移除，重复直至没有剩余区间。 O(n^2) 的时间复杂度。

其实这道题和 https://iamazing.cn/page/leetcode-435-non-overlapping-intervals 没啥大区别。

我们求出需要保留的当前区间，射爆它，之后找下一个需要保留的区间即可。

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) -> bool {
            return a[1] < b[1];
        });
        
        int count = 0;
        int lastEnd = INT_MIN;
        for (auto& p : points) {
            if (p[0] <= lastEnd) {
                continue;
            } else {
                count ++;
                lastEnd = p[1];
            }
        }
        return count;
    }
};

额，被 LeetCode 用 INT_MIN 偷袭了。。。

改成 long lastEnd = LLONG_MIN; 就好了。

Links: leetcode-452-minimum-number-of-arrows-to-burst-balloons