Minimum Number of Arrows to Burst Balloons
題目描述
給定氣球的水平直徑（以 [start, end] 表示），箭從某個 x 座標垂直射出，能射穿 start ≤ x ≤ end 的所有氣球。回傳射穿所有氣球所需的最少箭數。
輸入：points = [[10,16],[2,8],[1,6],[7,12]]
輸出：2
解釋：在 x=6 射穿 [2,8] 和 [1,6]，在 x=11 射穿 [10,16] 和 [7,12]
輸入：points = [[1,2],[3,4],[5,6],[7,8]]
輸出：4（完全不重疊，每個氣球都要一支箭）
解題思路
按右邊界排序
氣球按 end 值升序排列，例如 [[1,6],[2,8],[7,12],[10,16]] 排完後 end 依序為 6,8,12,16
射第一箭
在第一個氣球的右邊界射箭，arrowPos = 6。所有 start ≤ 6 的氣球都被射穿
檢查下一個氣球
如果氣球的 start ≤ arrowPos，代表這支箭能射穿它，直接跳過不需要新箭
需要新箭
如果 start > arrowPos，這個氣球超出當前箭的範圍，射新箭在它的右邊界，更新 arrowPos
計數箭數
每射一支新箭 arrows++，最終 arrows 就是最少箭數
程式碼
C#
public class Solution {
public int FindMinArrowShots(int[][] points) {
// 按右邊界排序
Array.Sort(points, (a, b) => a[1].CompareTo(b[1]));
int arrows = 1;
int arrowPos = points[0][1]; // 第一支箭的位置
for (int i = 1; i < points.Length; i++) {
if (points[i][0] > arrowPos) {
// 這個氣球沒被射到，需要新箭
arrows++;
arrowPos = points[i][1];
}
// 否則已被當前箭射穿，不用管
}
return arrows;
}
}TypeScript
function findMinArrowShots(points: number[][]): number {
points.sort((a, b) => a[1] - b[1]);
let arrows = 1;
let arrowPos = points[0][1];
for (let i = 1; i < points.length; i++) {
if (points[i][0] > arrowPos) {
arrows++;
arrowPos = points[i][1];
}
}
return arrows;
}Python
def findMinArrowShots(points: list[list[int]]) -> int:
points.sort(key=lambda x: x[1]) # 按右邊界排序
arrows = 1
arrow_pos = points[0][1]
for start, end in points[1:]:
if start > arrow_pos:
arrows += 1 # 需要新箭
arrow_pos = end # 射在右邊界
return arrows複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n log n) | O(1) |
- Time：排序需要 O(n log n)，之後一次線性遍歷 O(n)，排序主導所以整體 O(n log n)
- Space：排序可原地完成（in-place），只用了 arrows 和 arrowPos 兩個變數
邊界情況
- 只有一個氣球：不需要判斷，一支箭就夠，arrows 初始值 1 直接回傳
- 所有氣球完全重疊（如
[[1,5],[1,5],[1,5]]）：一支箭射穿全部，因為每個氣球的 start 都 ≤ arrowPos - 氣球只有邊界相觸（如
[[1,2],[2,3],[3,4]]）：每支箭都能順便射穿下一個（start == arrowPos算射穿），只需 1 支箭 - 大量氣球完全不重疊：每個氣球都需要單獨一支箭，arrows = n
圖解
圖表展示了貪心流程：先排序，然後射第一箭在最早結束的氣球右邊界。 每遇到一個氣球，檢查它的 start 是否在當前箭的範圍內。如果超出範圍就射新箭，否則已被射穿。
進階觀點
💡面試追問
Q: 和 435. Non-overlapping Intervals 的關係？ A: 本題的箭數 = 不重疊區間的最大組數。435 問「移除幾個才能不重疊」，答案 = n - 不重疊組數 = n - 箭數。兩題本質是同一個問題的正反面。
Q: 為什麼判斷用 > 而不是 >=？
A: 因為題目定義 start ≤ x ≤ end 都算射穿，所以邊界相觸（start == arrowPos）也能被射穿。如果用 >= 會把邊界相觸的情況誤判為需要新箭。
Q: 為什麼排序時用 a[1].CompareTo(b[1]) 而不是 a[1] - b[1]？
A: a[1] - b[1] 在大數字時可能整數溢位（例如 a[1] = 2^31 - 1, b[1] = -2^31），CompareTo 內部用比較而非相減，不會溢位。
Q: 可以按左邊界排序嗎？
A: 可以，但遇到重疊時需要更新 arrowPos 為 min(arrowPos, end)（保留較小的右邊界），邏輯稍微複雜。按右邊界排序更直覺，因為箭的位置天然就在右邊界。
理解測驗
🤔 為什麼箭要射在氣球的右邊界而不是左邊界？
🤔 氣球 [1,6] 和 [6,10]，一支箭能同時射穿嗎？