题目
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
提示:
1 <= intervals.length <= 105intervals[i].length == 2-5 * 104 <= starti < endi <= 5 * 104
思路
- 这题很像以前学的一道排课的题目——尽可能多地排课。
- 总体思路就是将所有区间升序排列，先把早开始的预排着，如果后面有在该区间内但是更早结束的，肯定就保留新的移除旧的，如果还晚则不如直接保留现有的对后续的影响更小。
- 若新的区间跟旧区间没重叠，直接跳过即可。
代码实现（不知道为什么我的时空间开销比别人大这么多）
class Solution {
public:
static bool myLess(vector<int> a, vector<int> b) {
if(a[0] > b[0]) return false;
else if(a[0] < b[0]) return true;
else return a[1] < b[1];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
int cnt = 0, startTime, endTime;
sort(intervals.begin(), intervals.end(), myLess);
if(intervals.empty()) return 0;
startTime = intervals[0][0];
endTime = intervals[0][1];
for(int i = 1; i < intervals.size(); ++i) {
// 没重叠
if(intervals[i][0] >= endTime) {
startTime = intervals[i][0];
endTime = intervals[i][1];
}
else {
// 若有重叠必然需要移除一个
cnt++;
// 若新区间在旧区间内，则新区间替换旧区间能释放更多的后续空间，所以替换
// 反之移除新区间
if(intervals[i][1] < endTime) {
startTime = intervals[i][0];
endTime = intervals[i][1];
}
}
}
return cnt;
}
};复杂度分析
- 时间复杂度：O(nlogn)——排序的时间复杂度。
- 空间复杂度：O(nlogn)——排序的栈空间的复杂度。
官方题解
- 看完官解总算发现问题了，可以看到我们循环中的比较其实跟startTime完全无关，所以其实排序的时候直接按endTime排序即可，可以减少至少一次比较，每次更新也能减少大约一次的startTime的赋值。
- 可行理由：这其实也是一个缩区间的过程，其实真正的比较就在于新区间起始和上一区间所达到的最大区间是否重叠，若无重叠直接更新即可，若有重叠则保留最早结束的区间，那么其实不用开始序排列，直接按结束序排列，开始序只在每次更新的时候作为判断而已。
- 这一步更新增加了一倍的效率，但还是很低，还得继续看。
- 第二点通过比较官解和本人的实现，内置的lambda表达式的效率似乎不如定义静态函数再调用效率高，因为lambda表达式调用过程是要生成一个匿名对象，调用的是对象的仿函数，因此每次都要比普通函数多一个构造过程，所以处理时间是会更久的。
- 第三点就是函数的值传递（太阴了），如果传的是一个容器，最好都传引用，否则每次函数调用都会发生一次拷贝，这个时间开销确实特别大，相当于上面的时空间复杂度应该都是O(n^2logn)的，所以效率才这么低。
- 第四点，如果排序的时候已经是按结束时间排序的，那么就不需要通过判断更新endTime了，因为新的endTime不可能大于旧的，所以那一步也可以省了。
- 优化后的代码如下
优化后代码实现
class Solution {
public:
static bool myLess(vector<int>& a, vector<int>& b) {
return a[1] < b[1];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
int cnt = 0, endTime, n = intervals.size();
if(intervals.empty()) return 0;
sort(intervals.begin(), intervals.end(), myLess);
endTime = intervals[0][1];
for(int i = 1; i < n; ++i) {
if(intervals[i][0] >= endTime) endTime = intervals[i][1];
else ++cnt;
}
return cnt;
}
};