Medium

题目描述

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

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

返回一个由每个区间 i 的 右侧区间 在 intervals 中对应下标组成的数组。如果某个区间 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
  • 每个区间的起点都 不相同

解题思路

这道题要求找到每个区间的右侧区间，即起点大于等于当前区间终点的最小起点区间。

思路分析：

  1. 暴力法： 对每个区间，遍历所有其他区间寻找满足条件的最小起点。时间复杂度 O(n²)，在数据量大时效率较低。

  2. 排序 + 二分查找（推荐）：

    • 首先创建一个包含起点和原始索引的数组，按起点排序
    • 对每个区间的终点，使用二分查找找到第一个大于等于该终点的起点
    • 由于题目保证起点唯一，二分查找能快速定位目标

  3. 双指针法： 也可以使用双指针技巧，但实现相对复杂。

核心思想： 通过排序将问题转化为在有序数组中查找第一个大于等于目标值的元素，这正是二分查找的经典应用场景。排序后的数组保存原始索引信息，确保能正确返回结果。

时间复杂度从 O(n²) 优化到 O(n log n)，空间复杂度 O(n)。

代码实现

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        int n = intervals.size();
        vector<pair<int, int>> starts; // {start, original_index}
        
        for (int i = 0; i < n; i++) {
            starts.push_back({intervals[i][0], i});
        }
        
        sort(starts.begin(), starts.end());
        
        vector<int> result(n);
        for (int i = 0; i < n; i++) {
            int end = intervals[i][1];
            // 二分查找第一个start >= end的位置
            int left = 0, right = n - 1, pos = -1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (starts[mid].first >= end) {
                    pos = starts[mid].second;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            result[i] = pos;
        }
        
        return result;
    }
};

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        n = len(intervals)
        starts = [(intervals[i][0], i) for i in range(n)]
        starts.sort()
        
        result = []
        for i in range(n):
            end = intervals[i][1]
            # 二分查找第一个start >= end的位置
            left, right = 0, n - 1
            pos = -1
            while left <= right:
                mid = (left + right) // 2
                if starts[mid][0] >= end:
                    pos = starts[mid][1]
                    right = mid - 1
                else:
                    left = mid + 1
            result.append(pos)
        
        return result

public class Solution {
    public int[] FindRightInterval(int[][] intervals) {
        int n = intervals.Length;
        var starts = new List<(int start, int index)>();
        
        for (int i = 0; i < n; i++) {
            starts.Add((intervals[i][0], i));
        }
        
        starts.Sort((a, b) => a.start.CompareTo(b.start));
        
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            int end = intervals[i][1];
            // 二分查找第一个start >= end的位置
            int left = 0, right = n - 1, pos = -1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (starts[mid].start >= end) {
                    pos = starts[mid].index;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            result[i] = pos;
        }
        
        return result;
    }
}

/**
 * @param {number[][]} intervals
 * @return {number[]}
 */
var findRightInterval = function(intervals) {
    const n = intervals.length;
    const starts = [];
    
    for (let i = 0; i < n; i++) {
        starts.push([intervals[i][0], i]);
    }
    
    starts.sort((a, b) => a[0] - b[0]);
    
    const result = [];
    for (let i = 0; i < n; i++) {
        const end = intervals[i][1];
        // 二分查找第一个start >= end的位置
        let left = 0, right = n - 1, pos = -1;
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (starts[mid][0] >= end) {
                pos = starts[mid][1];
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        result.push(pos);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)排序需要 O(n log n)，每个区间进行二分查找需要 O(log n)，总共 n 个区间
空间复杂度O(n)需要额外的数组存储排序后的起点和索引对

相关题目