[LeetCode] 452 | Minimum Number of Arrows to Burst Balloons | Python

---

문제 링크: 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 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 $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.

---

조건

• 1 <= points.length <= 105
• points[i].length == 2
• $-2^{31}$ <= $x_{start}$ < $x_{end}$ <= $2^{31}$ - 1

---

내 풀이

[[10,16],[2,8],[1,6],[7,12]]

입력이 위와 같이 주어졌을 때 이를 그림으로 표현하면 아래와 같이 표현된다.

결국 이 문제는 풍선들이 겹치는 가장 작은 범위들의 수를 구하는 것이다.

주어진 points를 오름차순으로 정리하고, 맨 처음 풍선의 시작과 끝을 각각 s1, e1이라 지정한다.

그 뒤의 풍선들을 차례로 겹치는 범위가 있는지 검사하는데, 겹치는 범위가 있다면 e1 = min(e1, e2)로 다시 지정한다.

s1을 재지정하지 않는 이유는 이미 points를 정렬해뒀기 때문이다.

풍선들을 검사하며 겹치는 범위가 없다면, s1와 e1을 s2와 e2로 새로 지정하며, ans를 1 키운다.

---

코드

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points = sorted(points)
        ans = 1
        s1, e1 = points[0]
        
        for s2, e2 in points[1:]:
            if s1 <= s2 <= e1:
                e1 = min(e1, e2)
            else:
                ans += 1
                s1, e1 = s2, e2
        
        return ans