【11月打卡~Leetcode每日一题】452. 用最少数量的箭引爆气球(难度:中等)
程序员文章站
2022-04-04 09:37:04
...
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)