LeetCode_二分搜索_中等_436.寻找右区间

1.题目

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

区间 i 的右侧区间可以记作区间 j，并满足 start_j >= end_i，且 start_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⁴
intervals[i].length == 2
-106 <= start_i <= end_i <= 10⁶
每个间隔的起点都不相同

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-right-interval

2.思路

（1）暴力穷举法
暴力穷举法比较容易想到，其具体步骤如下：
① 记 n = intervals.length 是区间个数，并定义长度为 n 的结果数组 res；
② 开始遍历每个区间：
1）第一层 for 循环：在针对每个区间 intervals[i] 时，分别用 minStart 和 minIndex 记录该区间对应的最小 start_j 以及对应的下标 j，初始值分别为 Integer.MAX_VALUE 和 -1；
2）第二层 for 循环：从第一个区间 intervals[j] 开始判断，如果 start_j ≥ end_i 并且 minStart ≥ start_j，那么就更新 minStart 和 minIndex；
3）第二层 for 循环结束后，直接用 res 来记录当前区间的右侧区间在 intervals 中对应下标组成的数组，即 res[i] = minIndex；
③ 所有区间遍历结束后，直接返回 res 即可。

（2）排序 & 二分搜索
我们可以在方法 1 的基础上进行时间复杂度的优化，在方法 1 的第 2 层 for 循环中，为了获得 minStart 和 minIndex，需要遍历所有的区间，显然其时间复杂度较高，所以优化的思路就是：
① 定义如下的二维数组 cloneIntervals，用于保存每个区间的起点以及每个区间在 intervals 中的下标；

// cloneIntervals 保存每个区间的起点以及每个区间在 intervals 中的下标
int[][] cloneIntervals = new int[intervals.length][2];
1
2

② 然后再将 cloneIntervals 按照区间的起点进行升序排序，这样就可以直接使用二分搜索算法来查找即可。

需要注意的是，本方法虽然降低了时间复杂度，但是由于需要额外定义数组 cloneIntervals，所以又提高了空间复杂度，即优化中常见的空间换时间。除此之外，由于题目要求的答案与 intervals 中区间的顺序有关，所以不能直接对 intervals 进行排序。

3.代码实现（Java）

//思路1————暴力穷举法
class Solution {
    public int[] findRightInterval(int[][] intervals) {
        //区间个数
        int n = intervals.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            int minStart = Integer.MAX_VALUE;
            int minIndex = -1;
            for (int j = 0; j < n; j++) {
                if (intervals[j][0] >= intervals[i][1]) {
                    if (minStart >= intervals[j][0]) {
                        minStart = intervals[j][0];
                        minIndex = j;
                    }    
                }
            }
            res[i] = minIndex;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//思路2————排序 & 二分搜索
class Solution {
    public static int[] findRightInterval(int[][] intervals) {
        //区间个数
        int n = intervals.length;
        int[] res = new int[n];
        // cloneIntervals 保存每个区间的起点以及每个区间在 intervals 中的下标
        int[][] cloneIntervals = new int[n][2];
        for (int i = 0; i < n; i++) {
            cloneIntervals[i] = new int[]{intervals[i][0], i};
        }
        //将 cloneIntervals 按照区间的起点进行升序排序(本题中每个间隔的起点都不相同)
        Arrays.sort(cloneIntervals, (interval1, interval2) -> interval1[0] - interval2[0]);
        for (int i = 0; i < n; i++) {
        	//从 cloneIntervals 找出大于等于 intervals[i][1] 的最小区间起点(即最左端点)
            int left = 0;
            int right = n - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (cloneIntervals[mid][0] < intervals[i][1]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            // left >= n 说明未能找到大于等于 intervals[i][1] 的起点
            res[i] = (left >= n) ? -1 : cloneIntervals[left][1];
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31