503. Find Right Interval

MediumBinary SearchBinary SearchSortingIntervals

Given a set of intervals (with unique start points), for each interval i find the 'right interval' — the interval j whose start is the smallest value greater than or equal to interval i's end. Return an array where the i-th entry is the index of that right interval, or -1 if none exists. The intervals are given as a JSON array of [start, end] pairs.

Input: A JSON array of [start, end] pairs.

Output: Array — right-interval indices (-1 if none).

Examples

Example 1
Input: [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Explanation: Interval 0 has no right; interval 1's right is index 0; interval 2's is index 1.
Example 2
Input: [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]
Explanation: Only interval 1 finds a right interval.
Example 3
Input: [[1,2]]
Output: [-1]
Explanation: Single interval.

Constraints

Asked by

MicrosoftAmazonBloombergGoogle
Solve this problem in the editor →