題目網址：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/

題意：有一些氣球貼在 XY 平面上, 給一 array points, 其中 points[i] = [x_start, x_end] 代表氣球水平直徑在 x_start 和 x_end 的氣球。

一支弓箭可沿著 x 軸完全垂直地射出。在座標 x 射出弓箭, 若有一個氣球的直徑滿足 x_start **≤** x **≤** x_end, 則該氣球會被引爆。弓箭被射出後, 可以無限地前進。

返回引爆所有氣球的最小弓箭數。

Solution 1：

想法：利用 Greedy, 每增加一支箭, 想辦法讓那支箭盡可能地引爆多一點的氣球。每一支箭的射出位置為「所有氣球中右邊界位置最靠左的」可以引爆最多氣球。如果某個氣球的起始點大於 end, 說明前面的箭無法覆蓋到當前的氣球, 那麼就得再來一支箭

e.g. points = [[1, 10], [2, 7], [8, 11]]+

  • 當只有 [[1, 10], [2, 7]] 時, 此時弓箭射在 x = 7 的位置可同時引爆這兩個氣球, 而下一個氣球的 start 必須 ≤ 7 才能用同一支箭引爆
  • 但下一個為 [8, 11], 所以必須要新增一支箭

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        // sort by start
        sort(points.begin(), points.end());

        int res = 1, end = points[0][1];

        for (int i = 1; i < points.size(); ++i) {
            if (points[i][0] <= end) { // 若有重疊, 則縮小右邊界, 必須考慮到先前的氣球
                end = min(end, points[i][1]);
            } else { // 若無重疊, 則更新右邊界, 換下一支箭
                end = points[i][1];
                ++res;
            }
        }

        return res;
    }
};

  • time：$O(n \cdot log(n))$ ➔ sorting
  • space：$O(1)$ ➔ 只需常數空間

Solution 2：

想法：同 Solution 1, 只是 sort by end

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        // sort by end
        sort(points.begin(), points.end(), [](const auto& a, const auto& b){
            return a[1] < b[1];
        });

        int res = 1, end = points[0][1];

        for (int i = 1; i < points.size(); ++i) {
            // 若無重疊, 則更新右邊界, 換下一支箭
            if (points[i][0] > end) {
                end = points[i][1];
                ++res;
            }
        }

        return res;
    }
};

  • time：$O(n \cdot log(n))$ ➔ sorting
  • space：$O(1)$ ➔ 只需常數空間