无重叠区间（435）

题目

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意

可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例

输入: [ [1,2], [2,3], [3,4], [1,3] ] 输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。

输入: [ [1,2], [1,2], [1,2] ] 输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

输入: [ [1,2], [2,3] ] 输出: 0

解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

算法

贪心

为了满足题目需要我们需要尽可能地选择短的区间，这样我们才能在之后尽可能地多放没有重叠的区间

为了判断是不是尽可能短地区间，我们可以通过其是不是早结束来判断，早结束的区间可以在之后拥有更多的无重叠区间，所以我们将每个区间按照结束位置递增地排序，然后我们选择第一个区间（结束最早的区间），使用变量right来保存这个区间的结束位置然后依次遍历找到第一个开始位置在其结束位置之后的区间，这两个区间之间遍历的便是重复的区间，我们需要递增变量res++来统计需要抛掉的区间。当我们找到下一个无重叠区间时，我们将新的结束位置right更改为这个区间的结束位置，然后继续判断

export const eraseOverlapIntervals = (intervals) => {
	if (intervals.length < 2) return 0;
	intervals.sort((a, b) => a[1] - b[1]);
	let right = intervals[0][1];
	let res = 0;
	for (let i = 1; i < intervals.length; i++) {
		if (intervals[i][0] >= right) {
			right = intervals[i][1];
		} else {
			res++;
		}
	}
	return res;
};