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;
};

參考資料