452.Minimum Number of Arrows to Burst Balloons
===

###### tags: `Medium`,`Array`,`Greedy`,`Sorting`

[452. Minimum Number of Arrows to Burst Balloons](https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/)

### 題目描述

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 verticall**y (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

### 解答

#### Javascript

function findMinArrowShots(points) {
  points.sort((a, b) => a[0] - b[0]);
  let count = 1;
  let end = points[0][1];
  for (let i = 1; i < points.length; i++) {
    if (points[i][0] > end) {
      count++;
      end = points[i][1];
    } else {
      end = Math.min(end, points[i][1]);
    }
  }

  return count;
}

> 這題跟merge intervals好像
> [name=Marsgoat] [time= Jan 5, 2023]

#### Python

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        bolloons = sorted(points, key=lambda x: x[1])
        
        first_balloon_end = bolloons[0][1]
        arrow = 1

        for balloon_start, ballon_end in bolloons:
            if balloon_start > first_balloon_end:
                arrow += 1
                first_balloon_end = ballon_end

        return arrow

> [name=Ron Chen] [time= Jan 6, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)