[Java/python3] 452. Minimum Number of Arrows to Burst Balloons

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

Minimum Number of Arrows to Burst Balloons - LeetCode

문제

한 지점 x좌표에 점을 찍어서, 최대한 많은 범위의 풍선을 터뜨리는 문제이다.

 

 

풀이

startPoint .. endPoint  있으면, endPoint 기준으로 오름차순 정렬을 하고, 화살 하나에 포함되는 풍선의 수가 최대한 많게 탐색하면 끝.

 

자바는 정렬할때 정수 오버플로우 발생함으로 주의할것. 

자바

class Solution {
    public int findMinArrowShots(int[][] points) {
        int cnt = 0;
        Arrays.sort(points, (o1, o2) -> {
            //return o1 - o2 하면 정수 오버플로우 발생 2 ^31-1 가 최대. 
            if (o1[1] == o2[1]) return 0;
            if (o1[1] < o2[1]) return -1;
            return 1;
        });
        
        int left = 0;
        long maxXpoints = 0;
        while(left < points.length ){
            cnt++;
               maxXpoints = points[left][1];
               int right = left+1;
               while(right < points.length && points[right][0] <= maxXpoints){
                    right++;
               }
            left = right;
        }
        return cnt;
    }
}

파이썬

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        p = sorted(points,key = itemgetter(1))
        left =0
        cnt = 0
        while left < len(p):
            cnt+=1
            max_x_points = p[left][1]
            right = left+1

            while right < len(p) and p[right][0] <=max_x_points:
                right +=1
            left = right if right > left+1 else left+1

        return cnt