Description
You are given an array of intervals where intervals[i] = [starti, endi]. For each interval i, find the smallest interval j such that startj >= endi. Return an array of right interval indices, or -1 if no such interval exists.
Examples
Input:
intervals = [[1,2]]Output:
[-1]Explanation:
No right interval exists.
Input:
intervals = [[1,4],[2,3],[3,4]]Output:
[-1, 2, -1]Explanation:
For [1,4] there is no right interval, for [2,3] the right interval is index 2, and for [3,4] there is none, so the result is [-1,2,-1].
Input:
intervals = [[1,1],[3,4],[2,2],[1,3]]Output:
[0,-1,2,1]Explanation:
For each interval, find the smallest start value >= its end value. [1,1]→index 0 (start>=1), [3,4]→-1 (no start>=4), [2,2]→index 0 (start>=2 found at [3,4] index 1, but smallest qualifying is index 0 with start=1... The right intervals are [3,-1,0,-1].
Constraints
- •
1 ≤ intervals.length ≤ 2 * 10^4