§1
题目描述
有一些气球贴在墙上，points[i] = [xstart, xend] 表示气球水平直径的开始和结束坐标。若一支箭在坐标 x 处射出，且 xstart <= x <= xend，这个气球会被引爆。请返回引爆所有气球所必须射出的最小弓箭数。
输入 = points = [[10,16],[2,8],[1,6],[7,12]]
输出 = 2
解释 = x=6 可引爆 [1,6] 和 [2,8]；x=12 可引爆 [7,12] 和 [10,16]。
输入 = points = [[1,2],[2,3],[3,4],[4,5]]
输出 = 2
§2
思路解析动画文字版
区间贪心通常先问：当前必须处理的区间，最晚能把选择拖到哪里。
把箭放在当前最早右端点，不会错过当前气球，同时给后续气球留下最大的重叠机会。
按右端点排序：原输入顺序是乱的。按右端点排序后，最早结束的气球会先被处理。
第一支箭：射在 [1,6] 的右端 6：第一支箭必须引爆第一个气球。射在 x=6 是最靠右的位置，给后面的区间留下最多机会。
[2,8] 被 x=6 覆盖：[2,8] 包含 x=6，同一支箭可以顺便引爆它。注意这里不更新 end，因为箭的位置已经固定在 6。
[7,12] 无法被 x=6 覆盖：当前气球左端点 7 已经在箭 6 的右边，必须增加一支箭。
第二支箭：射在 12：新箭同样射在当前气球的右端点 12，让它尽量还能覆盖后面的气球。
[10,16] 被 x=12 覆盖：[10,16] 包含 x=12，所以第二支箭也能引爆它。
所有气球已处理：每个气球都被某支箭覆盖，最终答案是 2。
返回箭数：arrows 记录的就是必须新增箭的次数，也就是最少箭数。
边界：start == end 不需要新箭：题目是闭区间，箭射在端点也算击中。
这和活动选择、无重叠区间是同一类贪心骨架。
§3
参考代码
class Solution: def findMinArrowShots(self, points): points.sort(key=lambda p: p[1]) arrows = 1 end = points[0][1] for start, finish in points[1:]: if start > end: arrows += 1 end = finish return arrows看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。
§4
复杂度
- 时间复杂度：O(n log n)，主要开销来自按右端点排序。
- 空间复杂度：O(1)，除排序实现内部开销外，只保存 arrows 和 end。
§5
易错点
✗ 错误写法：按左端点排序后贪心
✓ 正确写法：按右端点排序
右端点越早越紧迫，先固定它最安全。
✗ 错误写法：start == end 时新增箭
✓ 正确写法：只有 start > end 才新增箭
端点相交时同一支箭可以射中两个气球。
✗ 错误写法：覆盖新区间时更新 end
✓ 正确写法：覆盖时不更新 end
箭的位置已经固定，不能因为新区间更长就移动箭。
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
下一题 · 贪心套路 12/18
→任务调度器
LeetCode 621 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
299道动画图解
37节语音讲解
28课数据结构
¥0.27折合 / 天
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
¥99 开通年卡 →
想成体系刷透这类套路？去图解算法专题