目录
1 题目描述
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠
2 输入输出
示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
3 解答 使用贪心策略/使用动态规划
先计算最多能组成的不重叠区间个数，然后用区间总个数减去不重叠区间的个数。
在每次选择中，区间的结尾最为重要，选择的区间结尾越小，留给后面的区间的空间越大，那么后面能够选择的区间个数也就越大。
按区间的结尾进行排序，每次选择结尾最小，并且和前一个区间不重叠的区间。
这里的问题可以转为寻找不重叠区间的最大值。将区间按照最后一个数排序好，就可以使用贪心算法（贪心算法是一种特殊的动态规划，这里也可以使用动态规划解法）
1）定义子问题：寻找第k个区间前有多少区间不重叠（第k个区间最优解）
2）写出子问题的递推关系、找出边界关系：第一个区间为边界
递推关系：“寻找第k个区间前最多有多少区间不重叠”可以转为：假设前k-1个区间已经找出最多不重叠区间，如果第k个区间第一个数大于或等于前k-1个区间不重叠区间最后一项最后一个数 ------也即（第k个区间最优解=第k-1个区间最优解 + 1/0
3）选择动态规划的实现方法：动态规划有两种计算顺序，一种是自顶向下的、使用备忘录的递归方法，一种是自底向上的、使用 dp 数组的循环方法。
4）空间优化（可选）
附：时间空间复杂度分析
时间复杂度： O(nlog(n))。排序需要O(nlog(n)) 的时间。
空间复杂度：O(1)
4 代码
/**
* @param {number[][]} intervals
* @return {number}
*/
let eraseOverlapIntervals = function(intervals) {
if(intervals.length === 0){
return 0;
}
let result = 0; //表示不重叠区间的个数
let current = []; //表示不重叠矩阵区间当前项
intervals.sort((a, b) =>{ //对矩阵按照区间（矩阵中的项表示区间）的第二个数进行排序
return a[1] - b[1]; //从小到大排序
});
if(intervals[0].length === 2){
result = 1;
current = intervals[0];
}
for(let i = 1; i < intervals.length; i++){
if(intervals[i][0] >= current[1]){ //当前区间与前面不重叠区间最后一项进行比较，这里如果使用的intervals[i-1]项，会发生错误，因为该项不一定是不重叠区间项
result = result + 1;
current = intervals[i];
}
}
return intervals.length - result;
};
console.log(eraseOverlapIntervals([[1,100],[11,22],[1,11],[2,12]]));百里于2020年5月4日
如果有错，请您指出！如有侵权，请联系我删除！