354. Find Right Interval
You are given an array intervals where intervals[i] = [start_i, end_i] and every start value is distinct.
The right interval of interval i is the interval j whose start is the smallest start that is >= end_i. Note that j may equal i (an interval like [3, 3] is its own right interval), and equality counts: a start that lands exactly on end_i qualifies.
Return an array of n indices where entry i is the index of the right interval of interval i, or -1 if interval i has no right interval. Indices are 0-based and refer to positions in the original, unsorted input.
Example 1:
Input: intervals = [[3, 4], [2, 3], [1, 2]]
Output: [-1, 0, 1]
Explanation: [3, 4] has no start at or after 4. The right interval of [2, 3] is [3, 4] at index 0 (start 3 >= end 3). The right interval of [1, 2] is [2, 3] at index 1.
Example 2:
Input: intervals = [[1, 4], [2, 3], [3, 4]]
Output: [-1, 2, -1]
Explanation: No start reaches 4, so intervals 0 and 2 get -1. For [2, 3], start 3 (index 2) is the smallest start >= 3.
Example 3:
Input: intervals = [[1, 2]]
Output: [-1]
Explanation: The only interval has no start at or after its end 2.
Constraints:
- 1 ≤ intervals.length ≤ 2 * 10⁴
- -10⁶ ≤ start_i ≤ end_i ≤ 10⁶
- All start values are distinct.
Hints:
For one interval the question is: among all start values, which is the smallest one that is >= my end? Scanning all n starts for each of the n intervals answers it in O(n²).
"Smallest value >= x in a set" is exactly what binary search (lower_bound / bisect_left) computes on a sorted array. Sort the starts once — but pair each start with its original index first, because the answer must be reported in input order.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: intervals = [[3, 4], [2, 3], [1, 2]]
Expected output: [-1, 0, 1]