Java O(nlogn) solution base on BinarySearch [Accepted]


  • 1
    public int[] findRightInterval(Interval[] intervals) {
            int n = intervals.length;
            int[] results = new int[n]; 
            results[0] = -1;
            if (n == 1) return results;
            
            Interval[] temp = new Interval[n];
            // O(n)
            for (int i = 0; i < n; ++i){
                Interval value = new Interval(intervals[i].start, i);
                temp[i] = value;
            }
            
            //O(nlogn)
            Arrays.sort(temp, new Comparator<Interval>() {
    			@Override
    			public int compare(Interval o1, Interval o2) {
    				return o1.start - o2.start;
    			}
    		});
    		
    		//O(nlogn)
    		for (int i = 0; i < n; ++i){
    		    
    		    int left = 0;
    		    int right = n-1;
    		    int index = -1;
    		    while (left <= right){
    		        int mid = left + (right - left)/2;
    		        
    		        if (temp[mid].start == intervals[i].end){
    		            index = temp[mid].end;
    		            break;
    		        }
    		        else if (temp[mid].start > intervals[i].end){
    		            index = temp[mid].end;
    		            right = mid -1;
    		        }
    		        else{
    		            left = mid + 1;
    		        }
    		    }
    		    
    		    results[i] = index;
    		}
    		
    		return results;
        }
    

Log in to reply
 

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