题目：给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。
输入：[[1,2], [2,4], [1,3]]
输出：1
方法一：贪心算法
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& 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)，即为排序需要使用的栈空间。
