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

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

Leetcode - Minimum Number of Arrows to Burst Balloons

문제 유형 : 그리디, 정렬

문제 난이도 : Medium

 

문제

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.

 

풍선이 XY평면에 붙여져 있다. points[][]에 x좌표의 양끝을 알려준다.

y축의 방향으로 화살을 쏘는데, 풍선의 닫힌 구간에서 화살이 날아오면 풍선이 터진다.

모든 풍선을 터트리기 위한 최소 화살의 개수를 구하시오.

 

풀이

풍선의 오른쪽 끝 좌표를 기준으로 오름차순 정렬한다.

만약 현재 풍선의 왼쪽 끝이 이전 풍선의 오른쪽 끝보다 왼쪽에 있다면, 이전 화살에 맞은 것으로 처리시킨다.

그게 아니라면, 새 화살을 써야 하므로, 화살의 카운트를 1 늘리고, 이번 풍선부터 새로 묶음을 시작하기 위해 오른쪽 끝좌표를 저장시킨다.

이 과정을 모든 풍선에 대해 한 번씩 순회하면, 모든 풍선은 터지고, 최소 화살 개수가 저장되어 있다.

 

코드

C++

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), [](const auto &a, const auto &b){
            return a[1] < b[1];
        });

        int n = points.size();
        int arrows = 0;
        // 범위 처리를 위해
        long long end = -3e9;

        for (const auto &balloon : points) {
            if (balloon[0] > end) {
                arrows++;
                end = balloon[1];
            }
        }

        return arrows;
    }
};