Find Right Interval
Bloomberg LP● MediumNEW GRADPHONE SCREENProblem statement
You are given an array of intervals, where intervals[i] = [start_i, end_i] and every start value is unique.
For each interval i, find an interval j whose start is greater than or equal to end_i. Among all such intervals, choose the one with the smallest start.
Return an array of indices where result i is the chosen index j, or -1 when no right interval exists.
Function
findRightInterval(intervals: int[][]) → int[]Examples
Example 1
intervals = [[1,2]]return = [-1]No interval starts at or after 2.
Example 2
intervals = [[3,4],[2,3],[1,2]]return = [-1,0,1]Interval 0 has no right interval. Interval 1 chooses start 3 at index 0, and interval 2 chooses start 2 at index 1.
Example 3
intervals = [[1,4],[2,3],[3,4]]return = [-1,2,-1]Only interval 1 has a right interval: index 2 starts exactly at its end value 3.
Constraints
1 <= intervals.length <= 100000.- Each interval contains exactly two integers
[start, end]with-10^9 <= start <= end <= 10^9. - Every interval start value is unique.