LeetCode#452

LeetCode#452用最少数量的箭引爆气球

题目链接
U1S1，这个题目我读了好几遍（这是谁翻译的啊），题目的大概意思就是给你几个线段（气球），让你用最少的点把所有的线段都切断（打气球）。
一开始我甚至以为是个并查集。。。好久没做贪心了，这个题和有一个开会时间安排的题目有点类似（也是贪心算法，我找找回头再写水个题解吧）
思路也比较简单，首先对所有气球进行排序，排序规则是按照气球的尾部位置升序排序，如果尾部相同则按首部升序排序，然后只需要找到每个几个相邻气球的相邻范围就可以了，如果满足条件：points[i][1]>points[i+1][0]则相邻（上一个气球的尾部大于它下一个的首部）。然后不停的维护这个相邻区间，直到不相邻为止，再更新到新的区间继续找，直到找到整个数组的末尾即可：
附代码：

class Solution {
public:
    static bool cmp(vector<int>a,vector<int>b)
    {
        if(a[1]==b[1])
            return a[0]<b[0];
        return a[1]<b[1];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.size()<=1)
            return points.size();
        sort(points.begin(),points.end(),cmp);
        int f=0,ans=1;//f为当前不停维护的区间，判断下一个是否依然相邻        
        for(int i = 1 ; i < points.size() ; i++)
        {
            if(points[i][0]<=points[f][1])//相邻则维护区间，缩小范围
            {
                points[f][0]=max(points[f][0],points[i][0]);
                points[f][1]=min(points[f][1],points[i][1]);
            }
            else//不相邻则更新
            {
                ans++;
                points[f][0]=points[i][0];
                points[f][1]=points[i][1];
            }
        }
        return ans;
    }
};

还有就是，sort用的排序函数需要是static类型的，否则会报错（逃