Leetcode 452. Minimum Number of Arrows to Burst Balloons

tags: Leetcode(C++)

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

想法 :

​​​​Greedy，類似經典的社團活動題。
​​​​
​​​​用尾巴的大小排序，因為第一個區間總是需要被射掉，所以就以第一個區間當作指標開始射。
​​​​
​​​​如果下一個區間的開頭比現在的指標還要大了，那就代表我們需要第二枝箭了。
​​​​
​​​​以此往下遞推。
​​​​
​​​​證明 : 區間內射掉的某一個區間與現在的互換，不影響箭矢數量，反而有可能增加。

時間複雜度 : O(n)。

程式碼 :

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        int l=points.size(), ans=0, end;
        if(l == 0) return 0;
        if(l == 1) return 1;
        
        sort(points.begin(), points.end(), [](auto &v1, auto &v2){
            return v1[1] < v2[1];
        });
        
        /*for(int i=0 ; i<l ; i++){
            cout << points[i][0] << " " << points[i][1] << endl;
        }*/
        
        end=points[0][1];
        for(auto p:points){
            if(p[0] <= end) continue;
            else{
                ans++; end=p[1];
            }
        }
        
        return ++ans;
    }
};