Java O(n*logn) solution with explanation


  • 1

    Just keep in mind the some key points of this problem:

    First, create a new array that holds the every start of the intervals. To avoid the boundary problem, add two element whose value are Integer.MAX_VALUE and Integer.MIN_VALUE;
    Second, map the new array elements to their index, and after that it is safe to sort the arrays that we could still know what index the array's element belong to.
    Third, the reason we want to sort the new array is that we want binary search it to make the code more efficient.

    Here is the code:

    public class Solution {
        public int[] findRightInterval(Interval[] intervals) {
            int len = intervals.length;
            if(len < 2){
                return new int[]{-1};
            }
            
            int[] starts = new int[len + 2];
            int[] res = new int[len];
            Map<Integer, Integer> map = new HashMap<>();
            
            for(int i = 0; i < len; i++){
                starts[i] = intervals[i].start;
                map.put(starts[i], i);
            }
            starts[len] = Integer.MAX_VALUE;
            starts[len + 1] = Integer.MIN_VALUE;
            
            map.put(Integer.MAX_VALUE, -1);
            Arrays.sort(starts);
            
            for(int i = 0; i < len; i++){
                int end = intervals[i].end;
                res[i] = binarySearch(starts, map, end);
            }
            
            return res;
        }
        
        public int binarySearch(int[] starts, Map<Integer, Integer> map, int end){
            int low = 1;
            int high = starts.length - 2;
            while(high >= low){
                int mid = low + (high - low) / 2;
                if(starts[mid] > end && end > starts[mid - 1]){
                    return map.get(starts[mid]);
                }
                else if(starts[mid] < end){
                    low = mid + 1;
                }
                else{
                    high = mid - 1;
                }
            }
            
            return map.get(starts[low]);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.