困难

问题描述

一个整数区间 [a, b] ( a < b ) 代表着从 a 到 b 的所有连续整数，包括 a 和 b。

给你一组整数区间 intervals，请找到一个最小的集合 S，使得 S 里的元素与区间 intervals 中的每一个整数区间都至少有 2 个元素相交。

输出这个最小集合 S 的大小。

示例 1:

输入: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]
输出: 3
解释:
考虑集合 S = {2, 3, 4}. S 与 intervals 中的四个区间都有至少 2 个相交的元素。
且这是 S 最小的情况，故我们输出 3。

示例 2:

输入: intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]
输出: 5
解释:
最小的集合 S = {1, 2, 3, 4, 5}.

提示:

• intervals 的长度范围为[1, 3000]。
• intervals[i] 长度为 2，分别代表左、右边界。
• intervals[i][j] 的值是 [0, 108]范围内的整数。

贪心

将 $intervals$ 按右端点从小到大排列，若右端点相同，则按左端点从大到小排列。遍历 $intervals$ 中的区间，若当前区间的左端点大于集合的最大值时，说明当前记录集合跟区间无任何交集，需要从区间中取两个数加入到集合中，由于右端点是从小到大排列左端点从大到小排列的，将区间最右两个点加入到集合中，这两个点会最大程度上覆盖到后续右端点相同的区间，若当前区间的左端点小于等于于集合的最大值且大于集合次大值时，说明集合中的最大值已经覆盖了区间的一个点，只需再增加一个点即可，因此将区间的右端点加入到集合中，其余情况集合中都至少有两个点能覆盖到区间。由于添加过程数字是递增的，因此只需使用两个变量 $a$ 和 $b$ 分别代表当前集合的次大值和最大值即可。

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var intersectionSizeTwo = function (intervals) {
  intervals.sort((a, b) => a[1] - b[1] || b[0] - a[0])
  let ans = 0
  let a = -1
  let b = -1
  for (const interval of intervals) {
    if (interval[0] > b) {
      a = interval[1] - 1
      b = interval[1]
      ans += 2
    } else if (interval[0] > a) {
      a = b
      b = interval[1]
      ans += 1
    }
  }
  return ans
}

• 时间复杂度：$O(n\;log\;n)$
• 空间复杂度：$O(log\;n)$