用最少数量的箭引爆气球 图解题解

一支箭最少射几次，能引爆全部气球

给一组区间 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）同源：那题问最多留几个互不重叠的区间，这题问最少几个点穿透所有区间，本质都是排完右端后数不相交的分组。

Python

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

C++

int findMinArrowShots(vector<vector<int>>& points) {
    if (points.empty()) return 0;
    sort(points.begin(), points.end(),
         [](auto& a, auto& b){ return a[1] < b[1]; });  // 按右端升序
    int arrows = 1;
    long arrow = points[0][1];        // 第一箭射在第一个区间右端
    for (int i = 1; i < points.size(); i++) {
        if (points[i][0] > arrow) {   // 左端超过箭位
            arrows++;                 // 新加一支箭
            arrow = points[i][1];     // 射在当前区间右端
        }
    }
    return arrows;
}

Java

public int findMinArrowShots(int[][] points) {
    if (points.length == 0) return 0;
    Arrays.sort(points, (a, b) ->
        Integer.compare(a[1], b[1]));   // 按右端升序
    int arrows = 1;
    long arrow = points[0][1];          // 第一箭射在第一区间右端
    for (int i = 1; i < points.length; i++) {
        if (points[i][0] > arrow) {     // 左端超过箭位
            arrows++;                   // 新加一支箭
            arrow = points[i][1];       // 射在当前区间右端
        }
    }
    return arrows;
}