Binary Search Java Solution


  • 0
    public int[] findRightInterval(Interval[] intervals) {
    		
    	IntervalWithIndex[] orderedIntervals = new IntervalWithIndex[intervals.length];
    	for(int i=0;i<intervals.length;i++) {
    		orderedIntervals[i] = new IntervalWithIndex(intervals[i].start, intervals[i].end, i);
    	}
    	Arrays.sort(orderedIntervals, new IntervalComparator());
    	int[] rightIntervals = new int[intervals.length];
    	for(int i=0;i<intervals.length;i++) {
    		Interval interval = intervals[i];
    		int index = searchRightInterval(interval, 0, orderedIntervals.length-1, orderedIntervals);
    		rightIntervals[i] = index;
    	}
    	return rightIntervals;
    }
    	
    public int searchRightInterval(Interval current, int start, int end, IntervalWithIndex[] intervals) {
    	if(start>end) return -1;
    	int middle = (start+end)/2;
    	IntervalWithIndex middleInterval = intervals[middle];
    	if(current.end <= middleInterval.start) {
    		if(middle-1>=0 && current.end>intervals[middle-1].start) {
    			return middleInterval.index;
    		}
    		end = middle-1;
    	} else {
    		start = middle+1;
    	}
    	return searchRightInterval(current, start, end, intervals);
    }
    
    static class IntervalWithIndex extends Interval {
    	int index;
    	public IntervalWithIndex(int start, int end, int index) {
    		super(start,end);
    		this.index = index;
    	}
    }
    	
    static class IntervalComparator implements Comparator<Interval> {
    	public int compare(Interval i1, Interval i2) {
    		return i1.start-i2.start;
    	}
    }
    

Log in to reply
 

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