LC452算法模式区间 · 射气球区间时间轴

用最少数量的箭引爆气球

points=[[10,16],[2,8],[1,6],[7,12]] 最少箭。

题目是什么

points=[[10,16],[2,8],[1,6],[7,12]] 最少箭。

解决什么问题

当前区间与已确认边界是重叠、相离还是需要更新？

核心结论

按 end 排序,箭射当前 end,跳过被覆盖,下一未被盖需新箭。

01交互算法精讲

先说结论：这道题到底解决什么

怎样从“points=[[10,16],[2,8],[1,6],[7,12]] 最少箭。”推导出区间 · 射气球，并证明每次状态变化都不会漏掉答案？

中心结论：按 end 排序,箭射当前 end,跳过被覆盖,下一未被盖需新箭。

读完必须能回答

1.暴力方案在哪里重复计算，为什么仍然是正确基线？
2.当前区间与已确认边界是重叠、相离还是需要更新？
3.不变量“与无重叠区间对偶:箭=点,气球=区间。”为什么能保证算法安全前进？

02交互算法精讲

完整题目与题意拆解

points=[[10,16],[2,8],[1,6],[7,12]] 最少箭。

在本站主例中，points=[[10,16],[2,8],[1,6],[7,12]] 最少箭。

算法最终需要得到或观察：最少 2 箭。

把题目翻译成状态

• 输入：points=[[10,16],[2,8],[1,6],[7,12]] 最少箭。
• 机器需要维护：箭位置、排序、i。
• 最终可观察结果：最少 2 箭。

动画 1 · 题意扫描

先看清算法到底要维护什么

先建立输入、目标、输出和第一批状态，不急着进入模板。

Step 1/20%

题目与输入建立输入、目标与算法心智

在数轴上射箭,一支箭若穿过 x 则引爆该气球

正在加载算法场景...

发生了什么

points=[[10,16],[2,8],[1,6],[7,12]] 最少箭。

为什么

按 end 排序,箭射当前 end,跳过被覆盖,下一未被盖需新箭。

下一步

按坐标排序气球：sort points

当前状态

箭位置、排序、i。

当前 Go 代码 · 高亮第 3 行

1import "sort"2 3func findMinArrowShots(points [][]int) int {4    if len(points) == 0 { return 0 }5    sort.Slice(points, func(i, j int) bool {6        return points[i][1] < points[j][1]

03交互算法精讲

第一层方案：暴力做法

两两比较所有区间会重复检查重叠关系；排序后只需维护当前已合并边界或上一个结束点。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选，但没有保存已经确认的信息，因此同一状态会被重新计算。

动画 2 · 暴力重复

重复工作究竟发生在哪里

把重复读取或重复搜索的区域明确标出，再决定优化必须保存什么。

Step 1/20%

先做对：建立暴力基线枚举所有候选并完整验证

在数轴上射箭,一支箭若穿过 x 则引爆该气球

正在加载算法场景...

发生了什么

两两比较所有区间会重复检查重叠关系；排序后只需维护当前已合并边界或上一个结束点。

为什么

暴力法覆盖所有候选，因此可以作为题意校验版本；它的问题是重复工作，不是答案错误。

下一步

重复信息暴露出来：标出被重新计算的状态

当前状态

箭位置、排序、i。

当前 Go 代码 · 高亮第 4 行

1import "sort"2 3func findMinArrowShots(points [][]int) int {4    if len(points) == 0 { return 0 }5    sort.Slice(points, func(i, j int) bool {6        return points[i][1] < points[j][1]7    })

优化方向：按 end 排序,箭射当前 end,跳过被覆盖,下一未被盖需新箭。

04交互算法精讲

整体地图：先做什么，再做什么

1建模把输入翻译成“区间时间轴”，明确答案需要观察什么。
2状态只维护箭位置、排序、i。
3转移每一步按照按 end 排序,箭射当前 end,跳过被覆盖,下一未被盖需新箭。
4收尾读取最少 2 箭。，并复核边界与复杂度。

05交互算法精讲

区间时间轴：核心概念

排序把二维的任意关系压缩成从左到右的一次扫描。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：箭位置、排序、i。

核心不变量

• 与无重叠区间对偶:箭=点,气球=区间。

动画 3 · 核心概念

建立“区间时间轴”心智模型

用主例建立核心状态，先预测下一步，再公开正确分支和理由。

Step 1/30%

题目与输入建立输入、目标与算法心智

在数轴上射箭,一支箭若穿过 x 则引爆该气球

正在加载算法场景...

发生了什么

points=[[10,16],[2,8],[1,6],[7,12]] 最少箭。

为什么

按 end 排序,箭射当前 end,跳过被覆盖,下一未被盖需新箭。

下一步

按坐标排序气球：sort points

当前状态

箭位置、排序、i。

当前 Go 代码 · 高亮第 3 行

1import "sort"2 3func findMinArrowShots(points [][]int) int {4    if len(points) == 0 { return 0 }5    sort.Slice(points, func(i, j int) bool {6        return points[i][1] < points[j][1]

06交互算法精讲

核心机制：状态如何一步步变化

按 end 排序,箭射当前 end,跳过被覆盖,下一未被盖需新箭。

执行过程中持续维护：箭位置、排序、i。

正确性依赖以下不变量：与无重叠区间对偶:箭=点,气球=区间。

面试时可以压缩为：end 排序贪心 O(n log n)。

落到当前题，执行机制可以压缩为：按 end 排序,箭射当前 end,跳过被覆盖,下一未被盖需新箭。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

动画 4 · 机制构建

一次状态转移为什么成立

集中观察一次选择、计算和状态写回，让变量变化与原因同时出现。

Step 1/50%

气球 16 超出覆盖,需要新箭arrows++, anchor=p

x=16 在当前箭右侧,发射新箭

正在加载算法场景...

发生了什么

新箭锚在当前气球。

为什么

贪心:尽量让每支箭射在最右仍有效的位置。

下一步

预测下一步：暂停 · 由你判断

当前状态

anchor=10,arrows=2。

当前 Go 代码 · 高亮第 8 行

5    sort.Slice(points, func(i, j int) bool {6        return points[i][1] < points[j][1]7    })8    arrows, end := 1, points[0][1]9    for _, point := range points[1:] {10        if point[0] > end {11            arrows++

07交互算法精讲

正确性证明：为什么不会漏答案

初始化

初始化：算法开始时，全部合法候选仍在状态表示范围内；与无重叠区间对偶:箭=点,气球=区间。

保持

保持：执行“按 end 排序,箭射当前 end,跳过被覆盖,下一未被盖需新箭。”时，只删除已经能证明不可能的候选，并把新信息写回箭位置、排序、i。

终止

终止：没有待处理状态或达到命中条件时，当前可观察结果就是“最少 2 箭。”。

正确性抓手不是“样例跑通”，而是每一帧结束后仍能复述：与无重叠区间对偶:箭=点,气球=区间。

08交互算法精讲

完整执行过程

1题目与输入points=[[10,16],[2,8],[1,6],[7,12]] 最少箭。因为：按 end 排序,箭射当前 end,跳过被覆盖,下一未被盖需新箭。
2按坐标排序气球第一支箭必然需要。因为：至少一支箭覆盖第一个气球。
3气球 17 超出覆盖,需要新箭新箭锚在当前气球。因为：贪心:尽量让每支箭射在最右仍有效的位置。
4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5气球 18 超出覆盖,需要新箭新箭锚在当前气球。因为：贪心:尽量让每支箭射在最右仍有效的位置。
6气球 19 超出覆盖,需要新箭新箭锚在当前气球。因为：贪心:尽量让每支箭射在最右仍有效的位置。
7按坐标排序气球第一支箭必然需要。因为：至少一支箭覆盖第一个气球。
8收尾与复杂度最少 2 箭。因为：时间 O(n) · 空间 O(1)。按 end 排序,箭射当前 end,跳过被覆盖,下一未被盖需新箭。

动画 5 · 完整执行

从输入完整走到可观察结果

从主例第一帧运行到答案，时间轴始终显示当前状态、因果解释和下一步。

Step 1/80%

题目与输入建立输入、目标与算法心智

在数轴上射箭,一支箭若穿过 x 则引爆该气球

正在加载算法场景...

发生了什么

points=[[10,16],[2,8],[1,6],[7,12]] 最少箭。

为什么

按 end 排序,箭射当前 end,跳过被覆盖,下一未被盖需新箭。

下一步

按坐标排序气球：sort points

当前状态

箭位置、排序、i。

当前 Go 代码 · 高亮第 3 行

1import "sort"2 3func findMinArrowShots(points [][]int) int {4    if len(points) == 0 { return 0 }5    sort.Slice(points, func(i, j int) bool {6        return points[i][1] < points[j][1]

09交互算法精讲

把动画和 Go 代码逐行对应

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段，在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

动画 6 · 代码映射

让每个动作都落到 Go 分支

重新执行关键分支，只显示当前代码附近窗口，并说明这行为什么在此刻运行。

Step 1/60%

按坐标排序气球sort points

在数轴上射箭,一支箭若穿过 x 则引爆该气球

正在加载算法场景...

发生了什么

第一支箭必然需要。

为什么

至少一支箭覆盖第一个气球。

下一步

气球 16 超出覆盖,需要新箭：arrows++, anchor=p

当前状态

第一支箭锚在 10。

当前 Go 代码 · 高亮第 4 行

1import "sort"2 3func findMinArrowShots(points [][]int) int {4    if len(points) == 0 { return 0 }5    sort.Slice(points, func(i, j int) bool {6        return points[i][1] < points[j][1]7    })

10交互算法精讲

完整 Go 提交代码与最小测试

完整 Go 解法

import "sort"

func findMinArrowShots(points [][]int) int {
    if len(points) == 0 { return 0 }
    sort.Slice(points, func(i, j int) bool {
        return points[i][1] < points[j][1]
    })
    arrows, end := 1, points[0][1]
    for _, point := range points[1:] {
        if point[0] > end {
            arrows++
            end = point[1]
        }
    }
    return arrows
}

最小测试集合

func main() {
    // 1. 主例
    //    输入：mode="arrows", intervals=[[10,16],[2,8],[1,6],[7,12]]
    //    期望：最少 2 箭。
    //
    // 2. 失败 / 未命中
    //    检查：sort by end 同 435。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC435 无重叠；LC56 合并
}

11交互算法精讲

正确性与复杂度

时间复杂度 O(n)

执行过程中只保留仍可能影响答案的状态。按 end 排序,箭射当前 end,跳过被覆盖,下一未被盖需新箭。

空间复杂度 O(1)

额外状态主要用于维护：箭位置、排序、i。

终局不变量

• 与无重叠区间对偶:箭=点,气球=区间。

12交互算法精讲

最容易写错的地方

错误 1

sort by end 同 435。

边界复查

必须额外检查空输入、单元素、未命中或不可达情况，以及恰好落在边界的输入。

13交互算法精讲

最后复盘：带走逻辑链

1题意points=[[10,16],[2,8],[1,6],[7,12]] 最少箭。
2重复两两比较所有区间会重复检查重叠关系；排序后只需维护当前已合并边界或上一个结束点。
3优化按 end 排序,箭射当前 end,跳过被覆盖,下一未被盖需新箭。
4证明与无重叠区间对偶:箭=点,气球=区间。
5复杂度时间 O(n)，空间 O(1)

面试表达：end 排序贪心 O(n log n)。

迁移练习

• LC435 无重叠
• LC56 合并