Leetcode435:重叠区间——动态规划、贪心
目录
题目
https://leetcode-cn.com/problems/non-overlapping-intervals/
这题我竟然一年前做过，第二遍再做的时候一点印象都没有。
看了下提交记录，发现一年前做的时候代码还是自己敲上去的，一年之后咋就什么都不会了呢？难道我的算法水平还不如一年前？？？
题解
做的时候思路跑偏了，总想着把有重叠的区间找出来剔除掉。换一个思路，可以去寻找不重叠的最大区间数n，然后拿all-n就是最小重叠区间的数量。
贪心的解法其实不难理解，只是不太容易想到（因为我是菜鸡qwq）：
思路：可以把这题的情境想象成一个预定会议问题，区间的左右两端就是会议的开始时间和结束时间，要求会议时间不能重叠，寻找一个能安排最多会议次数的序列。那么我们先找到最先结束的那个会议，放在最开头。然后从剩下的会议里找到最先结束的，同时开始时间不早于第一个会议结束时间的那个会议，放在第二个。以此类推…就完成啦。
实际做题的时候有个技巧，就是可以先按照会议结束的时间（即区间右端点）进行排序。这样代码会好写很多。
上不是自己写的代码：
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 right = intervals[0][1];
int ans = 1;
for (int i = 1; i < n; ++i) {
if (intervals[i][0] >= right) {
++ans;
right = intervals[i][1];
}
}
return n - ans;
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/non-overlapping-intervals/solution/wu-zhong-die-qu-jian-by-leetcode-solutio-cpsb/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度分析：排序nlogn+遍历n，因为nlogn的幂次高，所以O(nlogn+n)=O(nlogn)，故时间复杂度O(nlogn)
空间复杂度：O(logn)，排序所需要的栈空间
还有一种动态规划的方法，是按照左端点进行排序，然后用f[i]表示「以区间 i 为最后一个区间，可以选出的区间数量的最大值」来进行状态转移。
代码比贪心复杂，时间复杂度也大一点，懒得去研究了。