0436. 寻找右区间【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 排序 + 二分查找

1. 📝 题目描述

• leetcode

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

区间 i 的 右侧区间 是满足 startj >= endi，且 startj 最小 的区间 j。注意 i 可能等于 j。

返回一个由每个区间 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 * 10^4
• intervals[i].length == 2
• -10^6 <= starti <= endi <= 10^6
• 每个间隔的起点都 不相同

2. 🎯 s.1 - 排序 + 二分查找

c

int cmp(const void* a, const void* b) {
    return ((int*)a)[0] - ((int*)b)[0];
}

int* findRightInterval(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize) {
    int (*sorted)[2] = malloc(sizeof(int[2]) * intervalsSize);
    for (int i = 0; i < intervalsSize; i++) { sorted[i][0] = intervals[i][0]; sorted[i][1] = i; }
    qsort(sorted, intervalsSize, sizeof(int[2]), cmp);
    int* res = (int*)malloc(sizeof(int) * intervalsSize);
    *returnSize = intervalsSize;
    for (int i = 0; i < intervalsSize; i++) {
        int target = intervals[i][1];
        int lo = 0, hi = intervalsSize;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (sorted[mid][0] >= target) hi = mid;
            else lo = mid + 1;
        }
        res[i] = lo < intervalsSize ? sorted[lo][1] : -1;
    }
    free(sorted);
    return res;
}

js

/**
 * @param {number[][]} intervals
 * @return {number[]}
 */
var findRightInterval = function (intervals) {
  const sorted = intervals.map((v, i) => [v[0], i]).sort((a, b) => a[0] - b[0])
  return intervals.map(([, end]) => {
    let lo = 0,
      hi = sorted.length
    while (lo < hi) {
      const mid = (lo + hi) >> 1
      if (sorted[mid][0] >= end) hi = mid
      else lo = mid + 1
    }
    return lo < sorted.length ? sorted[lo][1] : -1
  })
}

py

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        sorted_starts = sorted((iv[0], i) for i, iv in enumerate(intervals))
        res = []
        for _, end in intervals:
            lo, hi = 0, len(sorted_starts)
            while lo < hi:
                mid = (lo + hi) // 2
                if sorted_starts[mid][0] >= end:
                    hi = mid
                else:
                    lo = mid + 1
            res.append(sorted_starts[lo][1] if lo < len(sorted_starts) else -1)
        return res

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

算法思路：

• 将区间按左端点排序，记录原始索引
• 对每个区间的右端点，二分查找第一个左端点 $\ge$ 右端点的区间