中等

问题描述

给你一个区间数组 intervals ，其中 intervals[i] = [starti, endi] ，且每个 starti 都 不同 。

区间 i 的 右侧区间 可以记作区间 j ，并满足 startj >= endi ，且 startj 最小化 。

返回一个由每个区间 i 的 右侧区间 的最小起始位置组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。

示例 1：

输入：intervals = [[1,2]]
输出：[-1]
解释：集合中只有一个区间，所以输出-1。

示例 2：

输入：intervals = [[3,4],[2,3],[1,2]]
输出：[-1,0,1]
解释：对于 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间[3,4]具有最小的“右”起点;
对于 [1,2] ，区间[2,3]具有最小的“右”起点。

示例 3：

输入：intervals = [[1,4],[2,3],[3,4]]
输出：[-1,2,-1]
解释：对于区间 [1,4] 和 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间 [3,4] 有最小的“右”起点。

提示：

• 1 <= intervals.length <= 2 * 104
• intervals[i].length == 2
• -106 <= starti <= endi <= 106
• 每个间隔的起点都 不相同

排序

朴素的处理方式是使用一个额外数据存放 $intervals$ 按起始点从小到大排序以及原始下标记录，然后往后遍历，寻找符合右侧区间要求的记录，记录其原始下标。

/**
 * @param {number[][]} intervals
 * @return {number[]}
 */
var findRightInterval = function (intervals) {
  const n = intervals.length
  const arr = intervals.map((interval, index) => [index, interval[0], interval[1]]).sort((a, b) => a[1] - b[1])
  const ans = new Array(n).fill(-1)
  for (let i = 0; i < n; i++) {
    let j = i
    while (j < n && arr[i][2] > arr[j][1]) {
      j++
    }
    if (j < n) {
      ans[arr[i][0]] = arr[j][0]
    }
  }
  return ans
}

• 时间复杂度：$O(n^2 + n \, log \, n )$
• 空间复杂度：$O(n)$

实际上，如果我们按结束点从小到大的顺序去遍历，符合右侧区间要求的起始点也具有单调性。

使用两个额外的数组 $startIntervals$ 和 $endIntervals$ 分别记录基于所有区间的起始点和结束点从小到大排序以及它的原始下标。

依次取出 $endIntervals$ 中的值，再寻找符合右侧区间要求的起始点，由于起始点具有单调性，下一次循环时，无需重置指针，这样时间复杂度能够从 $O(n^2)$ 降为 $O(n)$。

/**
 * @param {number[][]} intervals
 * @return {number[]}
 */
var findRightInterval = function (intervals) {
  const n = intervals.length
  const startIntervals = intervals.map((interval, index) => [index, interval[1]]).sort((a, b) => a[1] - b[1])
  const endIntervals = intervals.map((interval, index) => [index, interval[2]]).sort((a, b) => a[1] - b[1])
  const ans = new Array(n).fill(-1)
  for (let i = 0, j = 0; i < n && j < n; i++) {
    while (j < n && endIntervals[i][1] > startIntervals[j][1]) {
      j++
    }
    if (j < n) {
      ans[startIntervals[j][0]] = endIntervals[i][0]
    }
  }
  return ans
}

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

二分查找

对于某一个区间 intervals[i] 而言，我们只关心目标区间的起始点。因此我们可以使用一个额外数据存放 $intervals$ 按起始点从小到大排序以及原始下标记录，然后就可以使用二分查找对目标进行搜索。

/**
 * @param {number[][]} intervals
 * @return {number[]}
 */
var findRightInterval = function (intervals) {
  const n = intervals.length
  const arr = intervals.map((interval, index) => [index, interval[0], interval[1]]).sort((a, b) => a[1] - b[1])
  const ans = new Array(n).fill(-1)
  for (let i = 0; i < n; i++) {
    let l = 0
    let r = n - 1
    while (l < r) {
      const mid = (l + r) >> 1
      if (arr[i][2] > arr[mid][1]) {
        l = mid + 1
      } else {
        r = mid
      }
    }
    if (arr[i][2] <= arr[r][1]) {
      ans[arr[i][0]] = arr[r][0]
    }
  }
  return ans
}

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