436. Find Right Interval

LeetCode 436. Find Right Interval

Description

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.

Return an array of right 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.

Tags

Binary Search

Solution

For each interval, we need to find if a value which is equal to or just greater than the interval's right interval exists in all left intervals. Thus, we needed a data structure that can search a given value very fast, and it can return an index where the value is either just greater than the target or return -1. Such data structure is a sorted array.

Based on the above analysis, the first step is to build a sorted array which contains all left intervals. Also, we need a hash table to store the map from a left interval to its index in intervals. The second step is to check if the search result of each right interval among the sorted array is valid. If the returned index is equal to the length of the array, we assign -1 to the corresponding position on the result array. Otherwise, assign start2idx[starts[startIdx]] to it.

Complexity

• Time complexity: $O(n\log(n))$

• Space complexity: $O(n)$

Code

func findRightInterval(intervals [][]int) []int {
	ans, starts, start2idx := make([]int, len(intervals)), make([]int, 0, len(intervals)), map[int]int{}
	// build a sorted array for start indices & a map from start to its index in intervals
	for i, interval := range intervals {
		if insertIdx := sort.SearchInts(starts, interval[0]); insertIdx == len(starts) {
			starts = append(starts, interval[0])
		} else {
			starts = append(starts[:insertIdx+1], starts[insertIdx:]...)
			starts[insertIdx] = interval[0]
		}
		start2idx[interval[0]] = i
	}
	// find and assign index to ans
	for i, interval := range intervals {
		if startIdx := sort.SearchInts(starts, interval[1]); startIdx == len(starts) {
			ans[i] = -1
		} else {
			ans[i] = start2idx[starts[startIdx]]
		}
	}
	return ans
}

Reference

1. 寻找右区间