[LeetCode] Medium - 452 Minimum Number of Arrows to Burst Balloons

▶452 - 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.

 

▶예제

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

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.

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

 

▶풀이

가장 먼저 points를 end(x[1]) 기준으로 정렬을 해준다.

그다음 하나씩 뽑아서 비교해주는 방식을 사용했다.

 

기본이 되는 shot을 points[0][1]로 두고, 다음부터 나오는 points의 start값들과 shot값을 비교해 준다.

만약에 shot보다 작다면 같이 터지기에 그대로 두었고,

크게 나온다면 터지지 않기에 shot값을 바꿔주고 answer를 1 증가시켜 줬다.

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

        for i in range(1, len(points)):
            if points[i][0] <= shot:
                continue
            else:
                shot = points[i][1]
                answer += 1
        
        return answer