My short Java binary search solution, beat 90%


  • 0
    F
    public int[] findRightInterval(Interval[] intervals) {
    	Map<Integer, Integer> map = new HashMap();
    	int[] starts = new int[intervals.length];
    	for (int i = 0; i < intervals.length; i++) {
    		starts[i] = intervals[i].start;
    		map.put(intervals[i].start, i);
    	}
    	Arrays.sort(starts);
    	
    	int[] res = new int[intervals.length] ;
    	for(int i=0;i<intervals.length;i++){
    		int end = intervals[i].end;
    		int index = Arrays.binarySearch(starts, end);
    		if(index >=0){
    			res[i] =  map.get(starts[index]);
    		}
    		else if(~index==intervals.length){
    			res[i] = -1;
    		}
    		else{
    			res[i]=map.get(starts[~index]);
    		}
    	}
    	return res;
    }

Log in to reply
 

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