452. Minimum Number of Arrows to Burst Balloons

Leetcode 问题: 452. Minimum Number of Arrows to Burst Balloons
Categories:
Tags:

题目

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

有不同大小的范围的气球，用最少的飞镖将所有气球射爆

传入气球大小阵列范围 [[2,8],[1,6],[7,12]]

索引 0 1 2 3 4 5 6 7 8 9 10 11 12
第 1 个气球范围 [2,8] V V V V V V V V
第 2 个气球范围 [1,6] V V V V V V
第 3 个气球范围 [7,12] V V V V V V

Example

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].
- Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].

答案

将气球大小按照每个大小的 终点 排序，然后从第一个气球 终点 射出第一隻箭

因为是按照 终点排序，所以其他气球的终点 一定比前面大

所以当其他气球的起点小于前面气球终点时，其他气球一定在射程范围，可以一次射爆

若 其他气球的起点 大于 前面气球终点，表示这个气球已经脱离射程范围了，需要另一把箭了

  1. 按照气球大小的 终点 排序所有连线，若终点相同，则将 长度越短 的气球大小排在前面
  2. 拿第一个气球 来当作参照比较，所以预设一定要射出 1 支箭
  3. 若目前「要检查的气球范围：起点」小于或等于「前一个气球范围区间：终点」，表示这个气球可以用上一个气球的飞镖射到，不需要额外的飞镖
  4. 若目前「要检查的气球范围：起点」大于「前一个气球范围区间：终点」，表示前一个气球的飞镖，射不到这个新的气球区间范围，需要新的飞镖
    • 拿最新射不到的气球来当作下一隻箭的参考点，将「新的气球区间范围的终点」，当作下一个飞镖的位置，继续检查下一个

JavaScript

/**
 * @param {number[][]} balloonsPointsList
 * @return {number}
 */
var findMinArrowShots = function(balloonsPointsList) {
    if (balloonsPointsList.length == 0) {
        // 如果没有任何资料，直接回传 0
        return 0;
    }

    // 排序清单大小(终点越小排前面)
    balloonsPointsList.sort((a, b) => {
        if (a[1] < b[1]) {
            // 当 a[1] 数字比 b[1] 小，a 较小排前面
            return -1;
        } else if (a[1] > b[1]) {
            // 当 a[1] 数字比 b[1] 大，a 较大排后面
            return 1;
        } else {
            // a[1] 数字 与 b[1] 一样大，表示终点一样，将长度较短的放在前面
            if (a[0] < b[0]) {
                // 当 a[0] 第一个数字比 b[0] 小，a 较长，a 排后面
                return 1;
            } else {
                // 当 a[1] 第一个数字比 b[1] 大，a 较短，a 排前面
                return -1;
            }
        }
    });

    // 射飞镖次数，预设为至少 1 个
    let arrowShot = 1;
    // 从第一个气球范围区间终点射飞镖，所以从这个点开始检查
    let previousEndPointer = balloonsPointsList[0][1];

    for (let i = 1; i < balloonsPointsList.length; i++) {
        // 从第 2 个气球区间开始检查，直到检查完所有气球区间
        // 取得目前要检查的气球范围
        let currentBalloonsPoint = balloonsPointsList[i];
        // 目前气球范围：起点
        let currentBalloonsStartPointer = currentBalloonsPoint[0];
        // 目前气球范围：终点
        let currentBalloonsEndPointer = currentBalloonsPoint[1];

        if (currentBalloonsStartPointer <= previousEndPointer) {
            // 若目前「要检查的气球范围：起点」小于或等于「前一个气球范围区间：终点」
            // 表示这个气球可以用上一个气球的飞镖射到，不需要额外的飞镖
            continue;
        } else {
            // 若目前「要检查的气球范围：起点」大于「前一个气球范围区间：终点」
            // 表示前一个气球的飞镖，射不到这个新的气球区间范围，需要新的飞镖
            arrowShot++;
            // 将「新的气球区间范围的终点」，当作下一个飞镖的位置，继续检查下一个
            previousEndPointer = currentBalloonsEndPointer;
        }
    }

    return arrowShot;
};

参考资料