[Leetcode/파이썬] 452. Minimum Number of Arrows to Burst Balloons

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] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. 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 xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. 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 <= 105
• points[i].length == 2
• -231 <= xstart < xend <= 231 - 1

 

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        arrows = 1
        points.sort(key=lambda x:x[1])
        target = points[0][1]

        for start, end in points[1:] :
            if target < start :
                arrows += 1
                target = end

        return arrows

그리디 알고리즘. 이 문제의 핵심은 범위에 타겟점을 하나 찍어 풍선을 터트리는 것으로, 가장 적은 화살을 쏘는 것이 문제에서 원하는 답이다. 

풍선 범위를 end에서 가장 작은 순으로 정렬하였다. 그 이유는 뒤로 갈수록 start가 target보다 작으면 화살을 한 발만 쏘더라도 다 터지며, start가 크다면 target arrow에 포함되지 않는 풍선이기 때문에 새로운 화살을 쏘아야 한다. 그리고 새로운 타겟을 해당 풍선의 end로 잡아야 똑같이 end보다 작은 start를 가진 풍선이 죄다 터질것이기 때문에 최소한의 화살을 쏘게 할 수 있다. 

쉽게 설명해 [1_start, 1_end] [2_start, 2_end]구조에서 1_end < 2_start  라면 2번째 풍선은 1번째 풍선과 겹치는 부분이 없기 때문에 새로운 화살을 쏴야 된다. 그리고 이를 반복한다. 

말은 쉬운데.. 문제 풀때는 이걸 생각하는게 쉽지 않네