452. 用最少数量的箭引爆气球

• 题号：452
• 来源：LeetCode
• 难度：中等
• 标签：贪心 排序 区间
• 语言：TypeScript
• 解法：2 个
• 作者：lmliheng
• 最近更新：2026-09-27

解法一

TypeScript · O(n log n) 时间 · O(1) 空间 · 更新于 2026-09-27

按左端点排序求区间交，注释自标有错

/**
 * @difficulty medium
 * @tags 贪心,排序,区间
 * @time O(n log n)
 * @space O(1)
 * @note 按左端点排序求区间交，注释自标有错
 * @452. 用最少数量的箭引爆气球
 */
let points: number[][] = [[1,9],[7,16],[12,17]]
// error : [[1,9],[7,16],[2,5],[7,12],[9,11],[2,10],[9,16],[3,9],[1,3]]
points.sort((a, b) => a[0] - b[0])
console.log(points)
let num = 1 //用于记录相同区间的res索引

let space: number[] = [...points[0]]
for (let i = 1; i < points.length; i++) {
    console.log(space)
    // 有公共区间
    if (points[i][0] <= space[1]) {
        space[0] = points[i][0]
        space[1] = Math.min(points[i][1], points[i - 1][1])

    } else {
        num++
        space[0] = points[i][0]
        space[1] = points[i][1]
    }
}

console.log(num)

源码：ts/leetcode/452. 用最少数量的箭引爆气球.ts

解法二 · TypeScript

TypeScript · O(n^2) 时间 · O(1) 空间 · 更新于 2026-09-27

按右端点排序，用首段右端删被覆盖区间

/**
 * @difficulty medium
 * @tags 贪心,排序,区间
 * @time O(n^2)
 * @space O(1)
 * @note 按右端点排序，用首段右端删被覆盖区间
 * @452. 用最少数量的箭引爆气球（解法二）
 */
let points = [[10, 16], [2, 8], [1, 6], [7, 12]];
points.sort((a, b) => a[1] - b[1]);
console.log(points);
let res = 0;
// 在 for循环中 一边遍历一边splice，从后往前遍历，避免索引变化导致的错误
// 也要删去0索引的区间
while (points.length > 0) {
    console.log("此时的第一个区间右侧是：", points[0][1]);
    for (let i = points.length - 1; i >= 0; i--) {
        if (points[i][0] <= points[0][1] && points[i][1] >= points[0][1]) {
            console.log("删除", points[i]);
            points.splice(i, 1);
        }
    }
    res++;
}
console.log(res);

源码：ts/leetcode/452. 用最少数量的箭引爆气球（解法二）.ts

---

在 GitHub 上查看题目所在目录：lmliheng/algorithm