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
intervals = [[1,2]][-1]No right interval exists.
intervals = [[1,4],[2,3],[3,4]][-1, 2, -1]For interval [1,4] at index 0: the requirement is start >= 4, but no interval starts at 4 or later, so -1. For interval [2,3] at index 1: the requirement is start >= 3, and interval [3,4] at index 2 starts at 3, so answer is 2. For interval [3,4] at index 2: the requirement is start >= 4, but no such interval exists, so -1.
intervals = [[1,1],[3,4],[2,2],[1,3]][3, -1, 0, -1]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