435. 无重叠区间
贪心解法
思路
首先将区间按右端点大小升序排序。那么第一个的右边界最小，给到下一个区间留的空间就更大。
局部最优：优先选择右边界小的区间，所以从左向右遍历，留给下一个区间的空间大，从而避免交叉
全局最优：选取最多的非交叉区间
特殊情况：首区间是 [2,3],[1,3] 排序后应该剔除哪个？对于这题来说其实都是一样的，可以任意选择，因为无论选择哪一个对于下一个区间的影响都是一样的，下一个区间只考虑其左端点是否小于首区间右端点，不在意首区间左端点的位置。
代码实现
class Solution { public: static bool cmp(vector<int> &a, vector<int> &b) { return a[1] < b[1]; } int eraseOverlapIntervals(vector<vector<int>> &intervals) { sort(intervals.begin(), intervals.end(), cmp); int pre = intervals[0][1], removed = 0; for (int i = 1; i < intervals.size(); i++) { if (intervals[i][0] < pre) { removed++; } else { pre = intervals[i][1]; } } return removed; } };
复杂度分析
时间复杂度：O(nlogn)，其中n是区间的数量。我们需要O(nlogn)的时间对所有的区间按照右端点进行升序排序，并且需要O(n)的时间进行遍历。由于前者在渐进意义下大于后者，因此总时间复杂度为O(nlogn)。
空间复杂度：O(logn)，即为排序需要使用的栈空间。
动态规划
思路
先将n个区间按右端点排序，然后使用动态规划方法求出区间最大值。令 fi 表示 以区间i为最后一个区间（包含i），可以选出的区间数量最大值
状态转移方程：
代码实现
class Solution { public: static bool cmp(vector<int> &a, vector<int> &b) { return a[1] < b[1]; } int eraseOverlapIntervals(vector<vector<int>> &intervals) { sort(intervals.begin(), intervals.end(), cmp); int n = intervals.size(); vector f(n, 1); for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (intervals[j][1] <= intervals[i][0]) { f[i] = max(f[i], f[j] + 1); } } } return n - *max_element(f.begin(), f.end()); } };
复杂度分析
时间复杂度：O ( n 2 )
空间复杂度：O ( n ) 即为存储所有状态 f i 需要的空间。
