Find Right Interval
Medium · Binary Search · Array · Binary Search · Sorting
Problem
You are given an array intervals where intervals[i] = [start_i, end_i], and every start_i is unique.
The *right interval* of interval i is the interval j with start_j >= end_i whose start_j is as small as possible. j may equal i, which happens when start_i == end_i.
Return an array whose i-th entry is the index of the right interval of interval i, or -1 if it has none.
Examples
Input: intervals = [[1,4],[5,6],[4,7]] Output: [2,-1,-1]
Interval 0 ends at 4 and interval 2 starts exactly at 4; nothing starts at or after 6 or 7.
Input: intervals = [[2,2],[0,1],[3,5]] Output: [0,0,-1]
Interval 0 is its own right interval; interval 1 ends at 1 and the smallest start at least 1 is 2, at index 0.
Input: intervals = [[3,8]] Output: [-1]
No interval starts at 8 or later.
Constraints
- 1 <= intervals.length <= 2 * 10^4
- intervals[i].length == 2
- -10^6 <= start_i <= end_i <= 10^6
- All start points are distinct
Approaches
- Baseline: try every interval — time O(n^2), space O(1) besides the output
Follow-up
Every start is distinct here, so the nearest start is one interval. The use cases search the other way, for the interval that ends latest before each start (ends may tie), and count every interval that starts after each one ends instead of picking the nearest.
Related problems
Start free on Cariara · Coding problems · System design studio
