LeetCode刷题DAY 38：用最少数量的箭引爆气球

戳蓝色字关注我们哟！

难度：中等 关键词：贪心算法、排序

⭐️⭐️⭐️

1

题目描述

有一堆交错排列的气球，求至少需要射出多少支箭才能将所有气球扎破。示例如下：

为方便描述，用数组points记录每个气球的两端点位置，points [i] = [xstart,xend]。

2

python实例展示

以三个气球为例，首先我们考虑一下气球排列时会出现的几种情况：

• 第一个气球和另两个气球都有重合，但是三个气球无重合

• 三个气球都不重合

• 三个气球都重合

• 两个气球重合，但这两个气球与第三个均不重合

由此可知，我们需要判断多个气球间的重合关系，来确认最少需要多少支箭。

思路

step 1: 根据每个气球的左端点，进行排序，并以当前气球的右端点为标杆

step 2: 判断下一个气球与当前气球是否有重叠

step 3: 如果有重叠则将重叠部分的最右端作为标杆；如无重叠则箭头数量加1且以不重叠气球右端点作为标杆

step 4: 重复步骤2、3，直至遍历结束

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return(0)
        points.sort()       
        
        b = points[0][1]
        nums = 0
        j=1
        while j<len(points):          
            if b>=points[j][0]:
                b = min(points[j][1],b)
            else:
                b = points[j][1]             
                nums+=1
            j+=1
        return(nums+1)

小思考：以上思路是先对左端点进行排序，然后根据右端点进行重叠部分的识别，那如果直接对右端点进行排序是否可以实现呢？ 后台回复“气球”获取答案