用最少数量的箭引爆气球
Minimum Number of Arrows to Burst Balloons
本机进度仅保存在当前浏览器
题目描述
在一个二维空间中有许多气球，每个气球用水平直径的坐标 [start, end] 表示。一支垂直射出的箭可以引爆所有与射线相交的气球（端点相触算相交）。求引爆所有气球所需的最少弓箭数。
示例：points = [[10, 16], [2, 8], [1, 6], [7, 12]]，输出 2。
解题思路
- 一支箭能引爆的气球集合 = 与某条竖线都相交的气球 = 一组"有公共交集"的区间。
- 按左端点排序后扫描，维护当前箭的公共交集右端 limit（各区间右端点的最小值）。
- 新气球左端 > limit 时交集断裂，需要新箭；否则 limit 收缩为 min(limit, 当前右端)。
参考实现
查看参考实现Python · 建议先自行作答
def findMinArrowShots(points):
points.sort(key=lambda x: x[0])
arrows = 1
limit = points[0][1]
for start, end in points[1:]:
if start > limit:
arrows += 1
limit = end
else:
limit = min(limit, end)
return arrows