452. Minimum Number of Arrows to Burst Balloons

Leetcode link

题目简介

/**
 * @param {number[][]} points
 * @return {number}
 */

题目给我们一个二维数字数组 points

每个数组元素代表一个气球的横向维度大小

我们可以纵向向气球射箭，而且箭可以射到无穷远

题目要求我们计算最少用几根箭可以射破所有气球

解题思路

这题有点像 435 的变体，本质上是让我们计算能包裹最多气球的重复区域

要求重复区域我们还是需要先对 points 升序排序

然后我们要记录一个最后的范围 last，保存当前重复区域的边界，在一开始我们将其初始化为 points[0]

接下来我们从 points[1] 开始遍历，每次判断第一个元素是否小于等于 last 第二个元素，如果是表示我们找到了重复区域，需要更新 last

否则我们需要的箭 +1，并且更新 last 为当前遍历的 point

最后返回需要的箭即可

Javascript

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function (intervals) {
    const len = intervals.length
    intervals.sort((a, b) => a[1] - b[1])
    let last = intervals[0][1]
    let res = 0

    for (let i = 1; i < len; i++) {
        if (intervals[i][0] < last) {
            res++
        } else {
            last = intervals[i][1]
        }
    }

    return res
};

复杂度分析

时间

O(nlogn)

空间

O(1)