Given a list of intervals, for each interval find the index of the minimum starting point interval that has a start >= current end. Return -1 if no right interval exists.
Input: [[1,2]] → Output: [-1]Input: [[3,4],[2,3],[1,2]] → Output: [-1,0,1]
Map each start point to its interval index. Sort start points. For each interval's end, binary search for the smallest start >= end.
- Build a TreeMap: startPoint -> original index.
- For each interval, use ceilingEntry(end) to find smallest start >= end.
- If found, record that index; else -1.
import java.util.*;
class Solution {
public int[] findRightInterval(int[][] intervals) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < intervals.length; i++)
map.put(intervals[i][0], i);
int[] result = new int[intervals.length];
for (int i = 0; i < intervals.length; i++) {
Map.Entry<Integer,Integer> entry = map.ceilingEntry(intervals[i][1]);
result[i] = entry == null ? -1 : entry.getValue();
}
return result;
}
}
- Time Complexity: O(N log N)
- Space Complexity: O(N)