# 資訊

:::info
- Question: 452. Minimum Number of Arrows to Burst Ballons
- From: Leetcode Daily Challenge 2024.03.18
- Difficulty: Medium
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

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 `x1-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:
:::success
- 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:
:::success
- 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:
:::success
- 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:
:::success
- 1 <= `points.length` <= $10^5$
- `points[i].length` == 2
- $-2^{31}$ <= `x_start` < `x_end` <= $2^{31} - 1$
:::

---

# 解法

## 概念

Greedy 題，也是很常見的 overlapping 問題

概念就是先選一個點射過去，然後再從沒破的氣球繼續選，不過怎麼選這個點就很重要，也就是 greedy 的核心

不出意外我又不夠 greedy 了，一開始我依照氣球的開頭 (`x_start`) 做排序，然後每次射的位置都選第一個還沒破的氣球的尾巴，一路做下去，但會發現如果遇到 `[[1,10],[2,9],[3,8],[4,7],[5,6]]` 這種測資，我會依序射 `[10,9,8,7,6]` 這樣，但其實會發現如果我直接射 `5` 或 `6` 就結束了，所以後面我改成對氣球的尾巴 (`x_end`) 做排序，然後一樣每次射的位置都選第一個還沒破的氣球的尾巴，排序後結果就是 `[[5,6],[4,7],[3,8],[2,9],[1,10]`，而按照 algorithm 我就會直接射到 `6`的確更 greedy！

## 程式碼

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort( key = lambda x:x[1])
        ans = 0
        curr = -1
        n = len( points )
        i = 0
        while i < n:
            curr = points[i][1]
            i += 1
            ans += 1
            while i < n:
                if curr >= points[i][0] and curr <= points[i][1]:
                    i += 1
                else:
                    break
        return ans

---

# 複雜度

## 時間複雜度

只少會走過整條 list，所以是 $O(n)$


## 空間複雜度

只有固定參數，所以是 $O(1)$