Java Binary Search O(logn) Solution


  • -1
    E

    The following is the solution using binary search. I code it for easy to understand without optimization. Hope it can help.

    public class Solution {
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            if(intervals.size()==0){
                intervals.add(newInterval);
                return intervals;
            }
            int l=0;
            int r=intervals.size()-1;
            int startInsertIndex=0;
            boolean startIntersect=false;
            int endInsertIndex=intervals.size()-1;
            boolean endIntersect=false;
            
            // Below logic to do the binary search, if the intersection found, the index will end at exact place.
            // if the intersection not found, the index is at the insert position.
            // sample:  [3,5], [7,9],[12,14]      insert[1,6] then:  startIntersect=0, endInsertIndex=1
            // index:   0      1     2
            while(l<=r){
                int mid=(r-l)/2+l;
                startInsertIndex=mid;
                if(intervals.get(mid).start>newInterval.start){
                    //search left side
                    r=mid-1;
                }else if(intervals.get(mid).end<newInterval.start){
                    //search right side
                    l=mid+1;
                }else if(intervals.get(mid).start<=newInterval.start && intervals.get(mid).end>=newInterval.start){
                    //found the intercept interval
                    startIntersect=true;
                    startInsertIndex=mid;
                    break;
                }
            }
            if(startIntersect==false && intervals.get(startInsertIndex).end<newInterval.start){
                //make sure index will be correct index if intersection not found.
                startInsertIndex++;
            }
            l=startInsertIndex; //this intersection can be at the same interval, so search from startInsertIndex to the end
            r=intervals.size()-1;
            while(l<=r){
                int mid=(r-l)/2+l;
                endInsertIndex=mid;
                if(intervals.get(mid).start>newInterval.end){
                    //search left side
                    r=mid-1;
                }else if(intervals.get(mid).end<newInterval.end){
                    //search right side
                    l=mid+1;
                }else if(intervals.get(mid).start<=newInterval.end && intervals.get(mid).end>=newInterval.end){
                    //found the intercept interval
                    endIntersect=true;
                    endInsertIndex=mid;
                    break;
                }
            }
            if(endIntersect==false && intervals.get(endInsertIndex).end<newInterval.end){
                //make sure index will be correct index if intersection not found.
                endInsertIndex++;
            }
         
            
            
            
            //System.out.println(startInsertIndex + ", " +endInsertIndex);
            if(startIntersect && endIntersect){
                Interval a_new = new Interval(intervals.get(startInsertIndex).start, intervals.get(endInsertIndex).end);
                for(int i=0; i<=(endInsertIndex-startInsertIndex); i++){
                    intervals.remove(startInsertIndex);
                }
                intervals.add(startInsertIndex, a_new);
                return intervals;
            }else if(startIntersect){
                Interval a_new = new Interval(intervals.get(startInsertIndex).start, newInterval.end);
                
                //meger all the interval in the middle, which means delete them
                if(startInsertIndex==endInsertIndex){
                    //remove one;
                    intervals.remove(endInsertIndex);
                }else{
                    for(int i=0; i<(endInsertIndex-startInsertIndex); i++){
                        intervals.remove(startInsertIndex);
                    }
                }
                intervals.add(startInsertIndex, a_new);
                return intervals;
            }else if(endIntersect){
                Interval a_new = new Interval(newInterval.start, intervals.get(endInsertIndex).end);
                
                //meger all the interval in the middle, which means delete them
                if(startInsertIndex==endInsertIndex){
                    //remove one;
                    intervals.remove(endInsertIndex);
                }else{
                    for(int i=0; i<=(endInsertIndex-startInsertIndex); i++){
                        intervals.remove(startInsertIndex);
                    }
                }
                intervals.add(startInsertIndex, a_new);
                return intervals;
            }else{
                //both start and end doesn't have intersection
                if(startInsertIndex==endInsertIndex){
                    //no need to merge any interval
                    intervals.add(startInsertIndex, newInterval); 
                    return intervals;
                }
                
                //meger all the interval in the middle, which means delete them
                for(int i=0; i<(endInsertIndex-startInsertIndex); i++){
                    intervals.remove(startInsertIndex);
                }
                intervals.add(startInsertIndex, newInterval);
                return intervals;
            }
        }
    }

Log in to reply
 

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