문제 링크

https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/?envType=study-plan-v2&envId=top-interview-150

문제 풀이

이번 문제는 최대로 겹치는 구간의 최소 개수를 세는 문제이다. 최소의 화살 갯수로 모든 풍선을 터트려야 하는 문제인데, 겹치는 구간에 화살을 쏘면, 하나의 화살로 여러개의 풍선을 터뜨릴 수 있다. 따라서 구간을 최대로 겹치도록 만들어서 해당 구간에 화살을 쏘아 화살 수를 줄여야 한다.

이때 화살의 개수를 추가해야하는 경우를 찾아보자. 첫 풍선 구간이 [1,5]라고 해보자. 이때, 화살 1개를 [1,5] 사이 어딘가에 쏘면 풍선을 터뜨릴 수 있다. 그런데 두번째 풍선이 [2,6] 이라고 하면, 화살을 [2,5] 사이에 쏘아야 두 풍선을 모두 터뜨릴 수 있다. 만약 1에 쏜다고 하면, 두 번째 풍선은 터지지 않기 때문에 화살이 하나 더 필요하다.

그런데, 만약 구간이 [6,7] 인 풍선이 있다고 해보자. 그러면 5에 화살을 쏘더라도 풍선을 해당 풍선을 터뜨릴 수가 없다. 즉, 현재 풍선의 마지막 끝점보다 더 나중에 시작하는 풍선이 있다면, 화살이 하나 더 필요하다.

즉, 풍선이 끝나는 지점을 기준으로 정렬하고, 끝나는 지점보다 시작하는 지점이 더 큰 곳에서 화살을 추가하면 최소의 화살 갯수를 구할 수 있다.

코드

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

        if (points.size() == 0) return 0;

        int ans = 1;
        int current_end = points[0][1];
        for (int i = 1; i < points.size(); ++i) {
            if (points[i][0] > current_end) {
                current_end = points[i][1];
                ans++;
            }
        }
        return ans;
    }
};