LeetCode 452 Minimum Number of Arrows to Burst Balloons

Tag: 贪心法 LeetCode Posted on 2022-02-21 17:09:44 Edited on 2022-02-21 17:21:58 Views: 137

概述

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; 就好了。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/