452. Minimum Number of Arrows to Burst Balloons

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Array,Greedy,Sorting

一、題目

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] = [x_start, x_end] denotes a balloon whose horizontal diameter stretches between x_start and x_end. 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 x_start and x_end is burst by an arrow shot at x if x_start <= x <= x_end. 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.

Example 1:

  • 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].

Example 2:

  • 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.

Example 3:

  • 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].

Constraints:

  • 1 <= points.length <= 10^5
  • points[i].length == 2
  • -2^31 <= x_start < x_end <= 2^31 - 1

二、分析

  • 這題是經典的區間問題，可以用 Greedy 的思維解，若要使一個集合的汽球用同一隻箭射破，它們必須要有一段重疊的區間，
  • 必須從左至右，或從右至左開始射箭，以避免兩端的留下汽球的情況發生。
  • 故我們使用 Sort 後，盡可能令愈多汽球與最左邊的汽球有重疊，方法是：
    • 由於 x_start 已經過排序，故只要後一顆汽球的比前一顆汽球的 x_end 還小，就表示有重疊。
    • 但要注意如果後一顆汽球的 x_end 比前一顆還小，那麼表示重疊的範圍需要縮小，故必須更新。

三、解題

1. Greedy

  • Time complexity: \(O(n\log n)\)
  • Space complexity: \(O(1)\)
int findMinArrowShots(vector<vector<int>>& points) {
    sort(points.begin(), points.end());
    int last = points[0][1];                // 右端點
    int cnt = 1;
    for (int i = 1; i < points.size(); i++) {
        if (points[i][0] <= last) {         // 只需比較右端點
            last = min(last, points[i][1]); // 重疊的範圍縮小，只需更新右端點
        } else {
            last = points[i][1];            // 若不重疊，則需再加另一隻箭，同時定義另一個重疊的區間
            cnt++;
        }
    }
    return cnt;
}

回目錄 Catalog