435. Non-overlapping Intervals

greedy O(nlogn)
思路很基本，维护一个当前全局结束时间，先按开始时间排序，再扫描看当前interval是否和当前全局最晚结束的一个interval有overlap（即当前interval的开始时间早于当前全局结束时间）

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(begin(intervals), end(intervals));
        int res = 0, e = INT_MIN;
        for (const auto &i : intervals) {
            if (i[0] < e) {
                ++res;
                e = min(e, i[1]);
            } else {
                e = i[1];
            }
        }
        return res;
    }
};

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int n = size(intervals);
        if (n < 2) return 0;
        sort(begin(intervals), end(intervals));
        int res = 0;
        for (int e = intervals[0][1], i = 1; i < n; ++i) {
            if (intervals[i][0] < e) {
                ++res;
                e = min(e, intervals[i][1]);
            } else {
                e = intervals[i][1];
            }
        }
        return res;
    }
};