Medium
Quiz
#436 Find Right Interval
APPROACH
You are given an array intervals where all start values are unique and intervals[i] = [starti, endi]. For interval i, its right interval is the interval j (possibly i itself) with the smallest start value that satisfies startj >= endi.
For each interval in order, return the original index of its right interval, or -1 when no such interval exists.
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.
1 of 4
1:00
What is the optimal approach for this problem?