[Leetcode] 452. Minimum Number of Arrows to Burst Balloons

문제

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

풀이

최대한 많은 구간을 포함할 수 있는 교집합을 찾아 하나의 그룹으로 묶는다. 이 그룹의 수가 답이 된다.

그럼 교집합을 찾아 하나의 그룹으로 묶는 방법을 생각해보자. 주어진 입력에 대해 이중 루프를 돌리면 $O(N^2)$이다. 그러나 다음과 같이 정렬을 해두면 한 번의 루프만으로도 찾을 수 있다.

• point[0] 에 대해 오름차순 정렬
• point[0]이 같으면 point[1]에 대해 오름차순 정렬

예를 들어 [[1,8],[2,7][7,10], [12,16]] 이라는 구간이 주어졌다고 하자. [1,8]과 [2,7]의 교집합은 [2,7]이다. 이 교집합과 [7,10]의 교집합을 다시 구하면 7이 남으므로 하나의 화살로 지금까지의 모든 풍선을 제거할 수 있다. [12,16]에는 7이 포함되지 않으므로 새로운 화살을 써야 한다. 따라서 답은 2이다. 정렬을 해두었기 때문에 순차적으로 교집합을 구할 수 있다.

코드

class Solution:
   def findMinArrowShots(self, points: list[list[int]]) -> int:
       sorted_points = sorted(points, key=lambda x: (x[0], x[1]))
       joint_right = sorted_points[0][1]
       arrow_count = 1
       
       for point in sorted_points:
            # 구간의 시작 지점(joint_left)은 비교할 필요가 없다. 정렬로 인해 다음의 조건이 모두 성립하기 때문이다.
            # 1. joint_left <= point[0]
            # 2. joint_left <= point[1] 
           if point[0] <= joint_right:
               joint_right = min(joint_right, point[1])
               continue
           
           joint_right = point[1]
           arrow_count += 1

       return arrow_count