[435] 无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回需要移除区间的最小数量，使剩余区间互不重叠 。

示例 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 <= 10^5

intervals[i].length == 2

-5> 10^4 <= starti < endi <= 5> 10^4

这是一道区间调度问题。

解题步骤分为以下几点：

1. 先对区间按照结束位置从小到大排序。并先选择第一个区间，即结束位置最小的区间。

2. 向后遍历，若当前区间的起始位置小于上一步中的结束位置，则说明这两个区间相交，将该区间剔除，count++。

3. 若不相交，则说明当前区间是一个不重叠的新区间，将选择结束位置移动到当前区间的结束位置。并重复上述步骤直到遍历完成。

不难看出，在排序后，这其实是一个贪心问题。通过判断俩区间 end 与 start 的关系，就能知道区间是否相交，从而使每一步都能选择出是否需要剔除当前区间。

function eraseOverlapIntervals(intervals: number[][]): number {
  let res = 0;
  // 先对 end 进行从小到大排序
  intervals.sort((a, b) => a[1] - b[1]);

  let end = intervals[0][1];
  for (let i = 1; i < intervals.length; i++) {
    const start = intervals[i][0];
    // 若该区间的起始点小于前一个区间的结束点，则说明该区间有重叠，需要被移除
    if (start < end) {
      res += 1;
    } else {
      // 否则找到了一个新的不重叠区间，将 end 指针移动过来
      end = intervals[i][1];
    }
  }
  return res;
}