Find Right Interval
Problem
Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the "right" of i.
For any interval i, you need to store the minimum interval j's index, which means that the interval j has the minimum start point to build the "right" relationship for interval i. If the interval j doesn't exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.
**Note:
- You may assume the interval's end point is always bigger than its start point.
- You may assume none of these intervals have the same start point.
Example 1:
Input: [ [1,2] ]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.
Example 2:
Input: [ [3,4], [2,3], [1,2] ]
Output: [-1, 0, 1]
Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.
Example 3:
Input: [ [1,4], [2,3], [3,4] ]
Output: [-1, 2, -1]
Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.
Solution
Binary Search Solution
public class Solution {
public int[] findRightInterval(Interval[] intervals) {
List<Integer> starts = new ArrayList<>();
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < intervals.length; i++) {
int start = intervals[i].start;
starts.add(start);
map.put(start, i);
}
Collections.sort(starts);
int[] res = new int[intervals.length];
for (int i = 0; i < intervals.length; i++) {
int end = intervals[i].end;
int start = binarySearch(starts, end);
if (start < end) res[i] = -1;
else res[i] = map.get(start);
}
return res;
}
private int binarySearch(List<Integer> starts, int target) {
int left = 0, right = starts.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (starts.get(mid) < target) left = mid + 1;
else right = mid;
}
return starts.get(left);
}
}
Analysis
We first collect all start into list starts
and index of each start to map
Then we sort the starts
and loop through interval to get next bigger element than it as start
If there is no such element, the returning value from binarySearch
will greater than target