戳蓝色字关注我们哟!
难度:中等 关键词:贪心算法、排序
⭐️⭐️⭐️
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)
小思考:以上思路是先对左端点进行排序,然后根据右端点进行重叠部分的识别,那如果直接对右端点进行排序是否可以实现呢? 后台回复“气球”获取答案