Leetcode刷题---435

题目：给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。
输入：[[1,2], [2,4], [1,3]]
输出：1
方法一：贪心算法

class Solution {
public:
    int eraseOverlapIntervals(vector>& intervals) {
        if (intervals.empty()){
            return 0;
        }
        sort(intervals.begin(), intervals.end(), [](const auto& u, const auto &v){
            return u[1] < v[1];
        });
        int n = intervals.size();
        int ans = 0, right = intervals[0][1];
        for (int i=1; i < n; ++i){
            if (intervals[i][0] < right){
                ++ans;
            } else {
                right = intervals[i][1];
            }
        }
        return ans;
    }
};

复杂度分析
时间复杂度：O(nlogn)，其中 n 是区间的数量。我们需要 O(nlogn) 的时间对所有的区间按照右端点进行升序排序，并且需要 O(n) 的时间进行遍历。由于前者在渐进意义下大于后者，因此总时间复杂度为 O(nlogn)。
空间复杂度：O(logn)，即为排序需要使用的栈空间。