Java nlogn solution, beats 98%, based on sort & binarySearch


  • 0
    A

    //Interval class was reused to store index;

    public int[] findRightInterval(Interval[] intervals) {
        if(intervals == null || intervals.length <= 1)
            return new int[]{-1};
        
        //create a new interval array, with original indexes;
        Interval[] orderedStartValuesAndIndexes = new Interval[intervals.length];
        for(int i=0; i<intervals.length; i++){
            orderedStartValuesAndIndexes[i] = new Interval(intervals[i].start, i);
        }
        Arrays.sort(orderedStartValuesAndIndexes, (i1, i2) ->i1.start-i2.start);
        
        int[] res = new int[intervals.length];
        for(int i=0; i<intervals.length; i++){
            res[i] = findMinRight(orderedStartValuesAndIndexes, intervals[i].end, 0, intervals.length-1);
        }
        return res;
    }
    
    //binary search the smallest which is >=  target
    //search space includes s(startIndex) and e(endIndex);
    public int findMinRight(Interval[] orderedItv, int target, int s, int e){
        if(s >= e){
            if(orderedItv[s].start >= target)
                return orderedItv[s].end;
            return -1;
        }
        //binary search
        int m = (s+e)/2;
        if(orderedItv[m].start < target){
            return findMinRight(orderedItv,  target,  m+1,  e);
        }else{
            return findMinRight(orderedItv,  target,  s,  m);
        }
    }

Log in to reply
 

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