452. Minimum Number of Arrows to Burst Balloons

[zeikar]

Problem link

https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons

Problem Summary

풍선의 x 좌표 구간이 주어질 때 수직으로 화살을 쏴서 전부 터뜨릴 수 있는 최소한의 화살 개수를 구하는 문제.

Solution

그리디로 풀면 된다. 먼저 정렬부터 해주자. 그런 다음 화살을 발사할 범위를 계속 계산하면서 가능한지 판단하면 된다.
좀 더 자세히 설명하면 겹치는 풍선의 범위를 계속 계산해나가면 된다. 풍선의 오른쪽 좌표의 최소값, minRight를 계속 갱신하면서 이전의 풍선들과 겹치는지 판단할 수 있고 현재 풍선의 왼쪽 x가 minRight보다 크면 이 풍선은 새로운 화살로 터뜨려야 한다.

처음에는 maxLeft, minRight 두 변수 썼었으나 maxLeft는 필요가 없었다...

Source Code

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points = sorted(points)

        cnt = 0
        minRight = -(1 << 32)
        for point in points:
            [left, right] = point

            if left > minRight:
                cnt += 1
                minRight = right
            else:
                minRight = min(minRight, right)

        return cnt