436. 寻找右区间

🟠 🔖 数组 二分查找 排序 🔗 力扣open in new window LeetCodeopen in new window

题目

You are given an array of intervals, where intervals[i] = [starti, endi] and each starti is unique.

The right interval for an interval i is an interval j such that startj >= endi and startj is minimized. Note that i may equal j.

Return an array ofright interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

Example 1:

Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Explanation: There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.

Example 3:

Input: intervals = [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]
Explanation: There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.

Constraints:

1 <= intervals.length <= 2 * 10^4
intervals[i].length == 2
-10^6 <= starti <= endi <= 10^6
The start point of each interval is unique.

题目大意

给你一个区间数组 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
每个间隔的起点都 不相同

解题思路

这题可以通过排序 + 二分查找高效解决。

保存区间起点和索引信息：
- 为了保留原数组的索引，将所有区间的 [start, end, index] 提取出来形成一个新数组 sortedArr。
对起点进行排序：
- 对 sortedArr 按起点从小到大排序，排序后，查找起点大于等于目标值时，可以利用二分查找高效完成。
遍历每个区间：
- 对于区间 i 的 end[i]，使用二分查找在 sortedArr 中找到第一个满足 start[j] >= end[i] 的区间。
- 如果找到符合条件的起点，将对应的索引加入结果数组；否则将 -1 加入结果数组。
返回结果数组

复杂度分析

时间复杂度：O(n logn).
- sortedArr 的排序时间复杂度为 O(n logn)；
- 对于每个区间进行一次二分查找，时间复杂度为 O(logn)，总共有 n 个区间，因此查找总复杂度为 O(n logn)；
- 总的时间复杂度为 O(n logn)。
空间复杂度：O(n)，sortedArr 和结果数组都占用了 O(n) 的空间。

代码

/**
 * @param {number[][]} intervals
 * @return {number[]}
 */
var findRightInterval = function (intervals) {
	const n = intervals.length;

	// 构建带原索引信息的新排序数组
	const sortedArr = intervals
		.map((item, idx) => [...item, idx])
		.sort((a, b) => a[0] - b[0]);

	// 结果数组
	let res = new Array(n);

	for (let [start, end, idx] of sortedArr) {
		let left = 0,
			right = n - 1;

		// 二分查找
		while (left <= right) {
			const mid = ((left + right) / 2) | 0;
			if (sortedArr[mid][0] < end) {
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}

		// 如果找到了符合条件的起点，加入对应索引，否则加入 -1
		res[idx] = left < n ? sortedArr[left][2] : -1;
	}
	return res;
};

436. 寻找右区间

# 436. 寻找右区间

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

436. 寻找右区间

题目

题目大意

解题思路

复杂度分析

代码

相关题目