435-无重叠区间

1. 问题
   给定一组区间，找出没有重叠区间最多的区间个数。

2. 思路[谷歌高畅力扣刷题笔记]
   贪心算法，贪心策略是优先保留结尾小且不相交的区间。
   首先根据右边界升序排序，然后依次比较左边界和前面的右边界：没有重叠就是满足条件的区间，有重叠就更新右边界。

3. 代码

    int eraseOverlapIntervals(vector>& intervals) {
        if(intervals.empty()) { // 没有元素
            return 0;
        }
        int n = intervals.size();
        sort(intervals.begin(), intervals.end(), [](vector& a, vector& b) {   // 根据右边界升序排列
            return a[1] < b[1];
        });
        int cnt=0, prev=intervals[0][1];    // prev代表右边界
        for(int i=1; i
            if(intervals[i][0] < prev) {    // 左边界不在前一个的范围内->没有相交部分
                cnt++;
            } else {    // 左边界在前一个的范围内->更新右边界
                prev = intervals[i][1];
            }
        }
        return cnt;
    }