欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【11月打卡~Leetcode每日一题】452. 用最少数量的箭引爆气球(难度:中等)

程序员文章站 2022-04-04 09:37:04
...

452. 用最少数量的箭引爆气球
【11月打卡~Leetcode每日一题】452. 用最少数量的箭引爆气球(难度:中等)
思路:使用贪心的思想,本题其实是一个求并集的题目,我们从x轴方向考虑,若一个气球需要被引爆,引爆点需要在[start,end]间,且肯定需要1根弓箭,那么我们要做的就是让这一根弓箭引爆更多的气球,即查找某个点的并集数量

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x:x[0])
        ans = 0
        while(points):
            s,e = points.pop(0)
            ans += 1
            while(points):
                s1,e1 = points[0]
                if s1>e:
                    break
                else:
                    s1,e1 = points.pop(0)
                    e = min(e1,e)
                        
        return ans

时间复杂度O(nlogn)
空间复杂度O(logn)