FindRightInterval.java

class FindRightInterval {
    public int[] findRightInterval(int[][] intervals) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int[] interval : intervals) {
            if (min > interval[0]) {
                min = interval[0];
            }
            if (max < interval[1]) {
                max = interval[1];
            }
        }
        int[] range = new int[max - min + 1];
        for (int i = 0; i < range.length; i++) {
            range[i] = -1;
        }
        for (int i = 0; i < intervals.length; i++) {
            range[intervals[i][0] - min] = i;
        }
        for (int i = range.length - 2; i >= 0; i--) {
            if (range[i] == -1) {
                range[i] = range[i + 1];
            }
        }
        int[] rightIntervals = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            rightIntervals[i] = range[intervals[i][1] - min];
        }
        return rightIntervals;
    }
}