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

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

Minimum Number of Arrows to Burst Balloons - LeetCode

Minimum Number of Arrows to Burst Balloons - Medium

 

풍선의 위치 정보가 담긴 벡터가 있다.

풍선의 위치는 [x_start, x_end] 로 주어지며, x_start부터 x_end까지 쭉 늘어져있다.

이 때, 화살을 이 사이에 두면 x_start, x_end 에 있는 모든 풍선이 터지게 된다.

이 때, 모든 풍선을 터뜨리기 위해 필요한 최소 화살의 개수는 몇개인지 구하는 문제다.

 

먼저 x_start 기준으로 오름차순으로 priority_queue pq를 만든다.

그 뒤, pq에서 가장 앞에 있는 풍선 위치(1)를 뽑아 화살을 x_end에 둬본다.

이렇게 하면 (1)의 풍선은 모두 터지게 된다.

그 다음 풍선 위치(2)를 뽑아보자. 

이 (2) 위치 사이에 (1)의 x_end가 포함된다면, (2) 역시 터지게 된다.

이 때, (1)의 x_end 보다 (2)의 x_end 가 작거나 같다면, 화살을 (2)의 x_end 위치로 바꿔준다.

이러면 (1)은 반드시 터지게 되고, 화살의 범위를 좁혀줄 수 있다.

 

만약 (2)의 x_first가 (1)의 x_end에 벗어난다면, 화살 개수를 한 개 늘리고, 앞 과정을 반복해주자.

 

이렇게 하면 풍선을 터뜨리기 위한 최소의 화살 개수를 구할 수 있다.

 

전체 풀이 코드

 

class Solution {
public:
    struct compare {bool operator()(pair<int, int>a, pair<int, int>b) {return a.first>b.first;}};
    int findMinArrowShots(vector<vector<int>>& points) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
        for (auto point:points) pq.push(make_pair(point[0], point[1]));
        int ret = 1, tmp = points[0][1];
        while (!pq.empty()) {
            pair<int, int> p = pq.top();
            pq.pop();
            if (p.first > tmp) tmp = p.second, ret++;
            else if (p.second <= tmp) tmp = p.second;
        }
        return ret;
    }
};