题目

题目来源：力扣（LeetCode）

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。
只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。

在完成所有删除操作后，请你返回列表中剩余区间的数目。

示例：

输入：intervals = [[1,4],[3,6],[2,8]]
输出：2
解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。

思路分析

贪心算法 是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

两个区间之间会有三种情况：

  • 相交
  • 不相交
  • 覆盖

所以需要比较两个区间的左边界和右边界的值。

我们首先对列表中的区间进行排序：将区间按左边界升序排序，如果左边界相同，则按区间右边界进行降序排序(为了便于知道是哪个区间覆盖哪个区间，我们将被覆盖的区间排到后面)。

初始化的时候，记录第一个区间的左边界和右边界：
leftStart = intervals[0][0];
rightEnd = intervals[0][1];

然后从排好序的列表的第二个区间开始遍历，判断当前区间的左边界和右边界与 leftStart 和 rightEnd 的大小关系：

  • 如果 当前区间的左边界 大于或等于 leftStart，并且当前区间的右边界 小于或等于 rightEnd，即 intervals[i][0] >= leftStart 并且 intervals[i][1] <= rightEnd ，说明当前遍历的区间是被区间 [leftStart, rightEnd] 覆盖的区间，则被覆盖区间的个数 +1 ；

  • 如果 当前区间的右边界 大于 rightEnd，即 intervals[1][0] > rightEnd ，说明当前遍历的区间与区间 [leftStart, rightEnd] 是不相交的，此时将 leftStart 和 rightEnd 的值更新为当前遍历的区间的左右边界值 (因为之前保存的区间 [leftStart, rightEnd] 已经与当前的遍历的区间不相交了，那么后面的区间都不会与区间 [leftStart, rightEnd] 相交，此时应该更新 leftStart 和 rightEnd 的值来继续判断后面的区间) ；

  • 如果 当前区间的左边界 小于或等于 rightEnd 并且 当前区间的右边界 大于或等于 rightEnd ，即 intervals[i][0] <= rightEnd 并且 intervals[i][1] >= rightEnd ，说明当前遍历的区间与区间 [leftStart, rightEnd] 是相交的，此时只需要将 rightEnd 的值更新为当前遍历的区间的右边界即可 (因为相交的区间是不可能互相覆盖的，所以需要得到最长的相交区间，只需要更新右边界即可: [leftStart(旧), rightEnd(新)])

若两个区间相交，则就可以将之前保存的区间 [leftStart,rightEnd] 中的右边界的值更新为更大的区间的右边界的值，并且只要后面有区间能够被这个扩大了的区间覆盖，则一定能够被该区间中某个存在的子区间覆盖。

示例

区间排序后：[[1, 4], [3, 6], [1, 2], [2, 8]] -> [[1, 4], [1, 2], [2, 8], [3, 6]]

第一个区间的左边界和右边界：leftStart = 1，rightEnd = 4

从第二个区间开始遍历：
i = 1，区间 [1, 2] 与 leftStart 和 rightEnd 作比较，1 <= 1 并且 2 <= 4（覆盖），count = 1；

i = 2，区间 [2, 8] 与 leftStart 和 rightEnd 作比较，4 >= 2 并且 4 <= 8（相交），rightEnd = 8：因为区间 [1, 4] 和 [2, 8] 相交，所以可将[leftStart, rightEnd] 扩大为 [1, 8]；

i = 3，区间 [3, 6] 与 leftStart 和 rightEnd 作比较，1 <= 3 并且 6 <= 8（覆盖），count = 2：区间 [3, 6] 被 [1, 8] 覆盖，所以在区间 [1, 8] 中一定存在某个子区间也可以将 [3, 6] 覆盖，容易看出区间 [2, 8] 可将 [3, 6] 覆盖。

  1. /**
  2.  * @param {number[][]} intervals
  3.  * @return {number}
  4.  */
  5. var removeCoveredIntervals = function(intervals) {
  6.   const length = intervals.length;
  7.   if (length === 0) return 0
  9.   intervals.sort((a, b) => {
  10.     // 左边界相同，按右边界降序排序
  11.     if (a[0] === b[0]) return b[1] - a[1];
  13.     return a[0] -b[0]; // 按左边界升序排序
  14.   });
  16.   let [leftStart, rightEnd] = intervals[0];
  17.   let count = 0;
  19.   for (let i = 1; i < length; i++) {
  20.     if (intervals[i][0] >= leftStart && intervals[i][1] <= rightEnd) { // 覆盖
  21.       count++
  22.     } else if (intervals[i][0] > rightEnd) { // 不相交
  23.       leftStart = intervals[i][0];
  24.       rightEnd = intervals[i][1];
  25.     } else if (intervals[i][0] <= rightEnd && intervals[i][1] >= rightEnd) { // 相交
  26.       rightEnd = intervals[i][1]
  27.     } else {
  28.       continue;
  29.     }
  30.   }
  32.   // 整体的区间数量 - 被完全包含的/被删除的区间 = 剩余的区间数量
  33.   return length - count
  34. };