题目描述
思路解析
一句话答案：LeetCode 452 用最少数量的箭引爆气球：把区间按右端升序排，一支箭钉在当前重叠组的最右端、左端越过箭位才新开一箭，时间 O(n log n)、空间 O(1)。
一支箭最少射几次，能引爆全部气球
给一组区间 points，每个 points[i]=[start, end] 是一个气球在水平方向占的一段范围。一支箭从某个 x 竖直射上去，凡是 start ≤ x ≤ end 的气球都会被引爆，要求箭最少。题面例子 points=[[10,16],[2,8],[1,6],[7,12]]，答案 2：一箭穿过 [1,6] 和 [2,8]，另一箭穿过 [7,12] 和 [10,16]。这等于把区间分成尽量少的几组，每组能被同一个 x 一起穿过。
挨个试哪些区间能共用一箭，会试到爆
枚举分组是第一反应：挨个试哪支箭罩哪几个区间、挑最少方案，可分法随区间数指数级涨，n 一大就配不完。换成先排序、再一趟扫过去边扫边定箭就快了——这是贪心：箭钉在当前重叠组的最右端就不再挪，后面区间自己往箭上靠、靠得着就连坐同爆。
按右端排序，箭钉在这一组的最右端
把区间按右端 end 从小到大排好，排完后第一个区间的右端，是全场最靠左的那条右边界——要引爆它，箭必须落在这条右边界之前。于是箭尽量往右挪，正好钉在它右端上：既打爆了它、又站到最靠右的落点，后面左端不超过箭位的区间全被顺带连坐、一起爆掉。
接着往后扫，每个区间只问一句：左端有没有越过当前箭的落点？没越过就和箭位有交集，白捡一个、箭不动；一旦左端超过箭位，这支箭最远只够到旧落点、再碰不到它，只能新开一箭钉在新区间右端。每次加箭都真省不掉，箭数便是最少。
加箭的判定，为什么卡在严格大于
加不加箭，卡在左端和箭位这一比：写成「左端 ＞ 箭位就加箭」，只有左端严格超过箭位，两者才真没交集。若左端恰好等于箭位，左边界正压在箭上、端点也算被穿过，箭仍打得中它、不该多加；松成「左端 ≥ 箭位」，端点相接的区间会被错判成够不着，箭数凭空多出。另外坐标能到 2^31−1，箭位用 32 位整数存会溢出，得用 64 位 long。
题面两组数据，各要几支箭
先看 points=[[10,16],[2,8],[1,6],[7,12]]，按右端排好是 [1,6]、[2,8]、[7,12]、[10,16]。第一箭钉在 [1,6] 右端，箭位 6，箭数 1。[2,8] 左端 2 ＞ 6 吗？不，箭位 6 落在里头，顺带爆掉。[7,12] 左端 7 ＞ 6，够不着了，新开一箭钉 12，箭数 2。[10,16] 左端 10 ＞ 12 吗？不，被 12 连坐。扫完 2 支，正是题面给的 2。
再看 points=[[1,2],[3,4],[5,6],[7,8]]，四段首尾都断开，排序后右端是 2、4、6、8。每一段的左端都 ＞ 前一个箭位（3＞2、5＞4、7＞6），支支都得新开一箭，谁也搭不上谁，一段一箭，答案 4。
复杂度与它的区间贪心近亲
耗时大头在排序，O(n log n)；排完只是线性扫一遍 O(n)，可忽略。额外只用箭位和箭数两个变量，空间 O(1)。这套「按右端排序 + 扫一遍」和无重叠区间（lc435）同源：那题问最多留几个互不重叠的区间，这题问最少几个点穿透所有区间，本质都是排完右端后数不相交的分组。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
为什么排右端、射右端？按右端排序后，第一个区间的右端是「最靠左的那条右边界」。要打中它，箭必须落在它的右端之前；而为了顺带多打几个，箭就尽量往右放——正好放在它的右端。等到某个区间的左端超过了当前箭位，说明它和这支箭再没有交集，只能开新箭。每次「不得不加箭」都是真省不掉的，所以箭数最少。
例 1 开始。先把区间按右端从小到大排好序（上面每格的数字就是排序后各区间的右端 end，下标是排序序号）。第一支箭等会儿就射在最左这个区间的右端。
处理排序后的第 1 个区间 [1,6]。直接在它的右端 x=6 射出第一支箭：既能打爆这个气球，又把箭放到了最靠右的位置，方便顺带打中后面左端 ≤ 6 的气球。
第一支箭定在 x=6（绿色高亮的就是箭所在的右端格），箭数记为 1。接下来每个区间只问一句话：它的左端 start 有没有超过当前箭位 6？没超过就被这支箭顺手打了，超过了才要加箭。
轮到区间 [2,8]（蓝光标）。当前那支箭还停在 x=6（绿色格）。只看一件事：这个区间的左端 2 有没有超过箭位 6？2 没超过它。
左端 2 没有超过当前箭位 6，说明现在这支箭（在 x=6）恰好落在这个区间里，气球已经被它一起打爆了。不用加箭，箭也不动（继续留在前面的右端，绿色格不变）。箭数还是 1。
轮到区间 [7,12]（蓝光标）。当前那支箭还停在 x=6（绿色格）。只看一件事：这个区间的左端 7 有没有超过箭位 6？7 比它大。
左端 7 已经超过了旧箭位 6——那支箭最远只到 6，再也碰不到这个区间。只能新开一支箭，射在它自己的右端 x=12（绿色格跳到这里）。箭数加一，变成 2。
轮到区间 [10,16]（蓝光标）。当前那支箭还停在 x=12（绿色格）。只看一件事：这个区间的左端 10 有没有超过箭位 12？10 没超过它。
左端 10 没有超过当前箭位 12，说明现在这支箭（在 x=12）恰好落在这个区间里，气球已经被它一起打爆了。不用加箭，箭也不动（继续留在前面的右端，绿色格不变）。箭数还是 2。
例 1 扫完：绿色高亮的每一格都是一支箭的落点（射在某个区间的右端）。一共加了 2 次箭，所以最少需要 2 支箭就能打爆全部气球。
例 2 开始。先把区间按右端从小到大排好序（上面每格的数字就是排序后各区间的右端 end，下标是排序序号）。第一支箭等会儿就射在最左这个区间的右端。
处理排序后的第 1 个区间 [3,5]。直接在它的右端 x=5 射出第一支箭：既能打爆这个气球，又把箭放到了最靠右的位置，方便顺带打中后面左端 ≤ 5 的气球。
第一支箭定在 x=5（绿色高亮的就是箭所在的右端格），箭数记为 1。接下来每个区间只问一句话：它的左端 start 有没有超过当前箭位 5？没超过就被这支箭顺手打了，超过了才要加箭。
轮到区间 [1,6]（蓝光标）。当前那支箭还停在 x=5（绿色格）。只看一件事：这个区间的左端 1 有没有超过箭位 5？1 没超过它。
左端 1 没有超过当前箭位 5，说明现在这支箭（在 x=5）恰好落在这个区间里，气球已经被它一起打爆了。不用加箭，箭也不动（继续留在前面的右端，绿色格不变）。箭数还是 1。
轮到区间 [2,8]（蓝光标）。当前那支箭还停在 x=5（绿色格）。只看一件事：这个区间的左端 2 有没有超过箭位 5？2 没超过它。
左端 2 没有超过当前箭位 5，说明现在这支箭（在 x=5）恰好落在这个区间里，气球已经被它一起打爆了。不用加箭，箭也不动（继续留在前面的右端，绿色格不变）。箭数还是 1。
轮到区间 [7,12]（蓝光标）。当前那支箭还停在 x=5（绿色格）。只看一件事：这个区间的左端 7 有没有超过箭位 5？7 比它大。
左端 7 已经超过了旧箭位 5——那支箭最远只到 5，再也碰不到这个区间。只能新开一支箭，射在它自己的右端 x=12（绿色格跳到这里）。箭数加一，变成 2。
轮到区间 [10,16]（蓝光标）。当前那支箭还停在 x=12（绿色格）。只看一件事：这个区间的左端 10 有没有超过箭位 12？10 没超过它。
左端 10 没有超过当前箭位 12，说明现在这支箭（在 x=12）恰好落在这个区间里，气球已经被它一起打爆了。不用加箭，箭也不动（继续留在前面的右端，绿色格不变）。箭数还是 2。
轮到区间 [15,17]（蓝光标）。当前那支箭还停在 x=12（绿色格）。只看一件事：这个区间的左端 15 有没有超过箭位 12？15 比它大。
左端 15 已经超过了旧箭位 12——那支箭最远只到 12，再也碰不到这个区间。只能新开一支箭，射在它自己的右端 x=17（绿色格跳到这里）。箭数加一，变成 3。
轮到区间 [14,18]（蓝光标）。当前那支箭还停在 x=17（绿色格）。只看一件事：这个区间的左端 14 有没有超过箭位 17？14 没超过它。
左端 14 没有超过当前箭位 17，说明现在这支箭（在 x=17）恰好落在这个区间里，气球已经被它一起打爆了。不用加箭，箭也不动（继续留在前面的右端，绿色格不变）。箭数还是 3。
轮到区间 [20,23]（蓝光标）。当前那支箭还停在 x=17（绿色格）。只看一件事：这个区间的左端 20 有没有超过箭位 17？20 比它大。
左端 20 已经超过了旧箭位 17——那支箭最远只到 17，再也碰不到这个区间。只能新开一支箭，射在它自己的右端 x=23（绿色格跳到这里）。箭数加一，变成 4。
轮到区间 [19,24]（蓝光标）。当前那支箭还停在 x=23（绿色格）。只看一件事：这个区间的左端 19 有没有超过箭位 23？19 没超过它。
左端 19 没有超过当前箭位 23，说明现在这支箭（在 x=23）恰好落在这个区间里，气球已经被它一起打爆了。不用加箭，箭也不动（继续留在前面的右端，绿色格不变）。箭数还是 4。
轮到区间 [26,28]（蓝光标）。当前那支箭还停在 x=23（绿色格）。只看一件事：这个区间的左端 26 有没有超过箭位 23？26 比它大。
左端 26 已经超过了旧箭位 23——那支箭最远只到 23，再也碰不到这个区间。只能新开一支箭，射在它自己的右端 x=28（绿色格跳到这里）。箭数加一，变成 5。
轮到区间 [25,30]（蓝光标）。当前那支箭还停在 x=28（绿色格）。只看一件事：这个区间的左端 25 有没有超过箭位 28？25 没超过它。
左端 25 没有超过当前箭位 28，说明现在这支箭（在 x=28）恰好落在这个区间里，气球已经被它一起打爆了。不用加箭，箭也不动（继续留在前面的右端，绿色格不变）。箭数还是 5。
例 2 扫完：绿色高亮的每一格都是一支箭的落点（射在某个区间的右端）。一共加了 5 次箭，所以最少需要 5 支箭就能打爆全部气球。
边界先想清：空数组 0 支；单区间 1 支；完全不重叠则有几个区间就几支；层层重叠的一支箭就够。贪心对这些都自洽。
两个高频追问：贪心正确性靠「按右端排序后每次加箭都不可避免」；它和无重叠区间是同一套右端贪心的两个变体。
参考代码
def findMinArrowShots(points): if not points: return 0 points.sort(key=lambda p: p[1]) # 按右端升序 arrows = 1 arrow = points[0][1] # 第一箭射在第一个区间的右端 for s, e in points[1:]: if s > arrow: # 左端超过箭位，够不到 arrows += 1 # 新加一支箭 arrow = e # 射在当前区间的右端 return arrows复杂度
- 时间：O(n log n)，排序主导；排完后只扫一遍 O(n)
- 空间：O(1)~O(n)，只用 arrow/arrows 两个变量；排序所需栈空间视实现而定
易错点
面试追问把动画讲成自己的话
追问为什么按右端排序、把箭放在右端能保证箭数最少？
追问它和「无重叠区间 / 区间调度」是不是一类？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最小时间差
LeetCode 539 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题