Find Right Interval

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:

1. You may assume the interval's end point is always bigger than its start point.
2. 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.

Basically we need to sort the array, then for each interval, search all nodes to its right and find the first one that has start greater than its end. Searching for the first "right" node can have multiple ways, the most efficient way is to use binary search. But the easiest way is, to just traverse the nodes to its right and find the first right node.

I used a structure to track the original index of the interval. Alternatively we can also do it by using maps.

public int[] findRightInterval(Interval[] intervals) {
        int len = intervals.length;
        int[] rst = new int[len];
        if (len == 0) {
            return rst;
        }
        
        IntervalNode[] intervalNodes = new IntervalNode[len];
        int pos = 0;
        for (int i = 0; i < len; i++) {
            intervalNodes[pos++] = new IntervalNode(intervals[i], i);
        }
        
        Arrays.sort(intervalNodes, new Comparator() {
           @Override 
           public int compare(IntervalNode in1, IntervalNode in2) {
               if (in1.interval.start != in2.interval.start) {
                   return in1.interval.start - in2.interval.start;
               } else {
                   return in1.index - in2.index;
               }
           }
        });
        for (int i = 0; i < len; i++) {
            IntervalNode curr = intervalNodes[i];
            int end = curr.interval.end;
            int j = i + 1;
            
            while (j < len && curr.interval.end > intervalNodes[j].interval.start) {
                j++;
            }
            rst[curr.index] = j == len ? - 1 : intervalNodes[j].index;
        }
        return rst;
    }
    
    private class IntervalNode {
        Interval interval;
        int index;
        
        public IntervalNode(Interval interval, int index) {
            this.interval = interval;
            this.index = index;
        }
    }