LeetCode (C/C++) 452. Minimum Number of Arrows to Burst Balloons

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

---

풀이

수의 범위가 int형의 범위이므로 수를 저장하는 방식으로는 풀지 못 하겠다고 판단했다.

 

현재 풍선의 범위와 다음 풍선들의 범위 중 겹치는 부분들만 남겨두어 하나의 화살로 터트릴 수 있는 풍선의 최대 개수를 구했다. 범위가 겹친다면 하나의 화살로 풍선을 터뜨릴 수 있으므로 둘 중 좁은 범위를 구해 겹치는 부분을 갱신하고, 다음 풍선의 범위를 탐색했다.

 

+

start 값은 없어도 됨

---

코드

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        // 오름차순으로 정렬
        sort(points.begin(), points.end());

        int cnt = 0, now = 0, idx = 1;
        int size = points.size();
        
        while (now < size) {

            // 현재 인덱스 기준으로 [start, end] 범위를 지정
            int start = points[now][0], end = points[now][1];

            // idx를 늘려가며 [start, end] 범위를 좁혀감 -> 하나의 화살을 쏠 때 터뜨릴 수 있는 풍선의 개수 구함
            while (idx < size && !(end < points[idx][0] || points[idx][1] < start)) {
                start = max(start, points[idx][0]);
                end = min(end, points[idx][1]);
                idx++;
            }

            cnt++;
            now = idx, idx += 1;
        }
        return cnt;
    }
};