// Hash table solution: use NavigableMap find the ceilingEntry every time
// Time: O(n) * O(logn) = O(nlogn) where O(logn) is the time complexity of NavigableMap.ceilingEntry(), 21ms
// Space: O(n), 47.4mb
import java.util.NavigableMap;

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        
        // Make a map of <begin time, index of interval>
        NavigableMap<Integer, Integer> map = new TreeMap<>();
        for(int i = 0; i < intervals.length; i++) {
            map.put(intervals[i][0], i);
        }
        
        // Find the ceilingEntry for each interval
        int[] ans = new int[intervals.length];
        for(int i = 0; i < intervals.length; i++) {
            Map.Entry<Integer, Integer> entry = map.ceilingEntry(intervals[i][1]);
            ans[i] = entry == null ? -1 : entry.getValue();
        }
        
        return ans;
    }
}