~1ms O(n) Java solution to insert interval (better than 99.66%)


  • 1
    S
    1. Do two binary searches to find the start and end interval of the interval being inserted. One binary search comparing the interval being inserted's start value to the start values in the intervals in the list and the other comparing the interval being inserted's end value to the start values of intervals in the list.

    2. Handle all of the possible cases of where the interval being inserted lies in regards to the intervals returned from binary search

    public class Solution {
    
         public Solution()
         {}
    
         public List<Interval> insert(List<Interval> intervals, Interval newInterval)
         {
             if(newInterval == null)
                 return intervals;
             
             if(intervals.size()<1)
             {
                  intervals.add(newInterval);
                  return intervals;
             }
    
             int startIndex = binarySearch( intervals,newInterval.start);
             int endIndex = binarySearch( intervals,newInterval.end);
             
             Interval startInterval;
             Interval endInterval;
             
             if(startIndex==-1)
              startInterval = intervals.get(startIndex+1);
             else
               startInterval = intervals.get(startIndex);
             
             if(endIndex==-1)
              endInterval = intervals.get(endIndex+1);
             else
               endInterval = intervals.get(endIndex);
    
             if(startIndex==-1 && endIndex>=intervals.size()-1)
             {
                 intervals = new ArrayList<Interval>();
                 newInterval.end = Math.max(newInterval.end, endInterval.end);
                 intervals.add(newInterval);
             }
             else if (startIndex== endIndex)
             {
                 if(startIndex==-1)
                 { 
                    intervals.add(0,newInterval);
                 }
                 else  if(newInterval.start<=endInterval.end &&newInterval.end>endInterval.end)
                 {
                       endInterval.end = newInterval.end;
                       intervals.set(startIndex,endInterval);
    
                 }
                 else if(newInterval.start>endInterval.end &&newInterval.end>endInterval.end)
                 {
                       intervals.add( endIndex +1,newInterval);
                 }
             }
             else if(startIndex==-1 )
             {
                 for(int i=0; i<endIndex; i++)
                 {
                     intervals.remove(0);
                 }
    
                 endInterval.start = newInterval.start;
                 endInterval.end = Math.max(newInterval.end, endInterval.end);
                 intervals.set(0, endInterval);
             }
             else if(endIndex>=intervals.size()-1)
             {
                for(int i=endIndex; i>startIndex; i--)
                {
                    intervals.remove(intervals.size()-1);
                }
    
                if(startInterval.end>=newInterval.start)
                {
                    startInterval.end = Math.max(newInterval.end, endInterval.end);
                    intervals.set(startIndex,startInterval);
                }
                else
                {
                     endInterval.start = newInterval.start;
                     endInterval.end =  Math.max(newInterval.end, endInterval.end);
                     intervals.add(endInterval);
                }
             }
             else
             {
                for(int i=endIndex-1; i>startIndex; i--)
                {
                     intervals.remove(i);
                }
    
                if(startInterval.end>=newInterval.start)
                {
                     startInterval.end = 
                    		 Math.max(endInterval.end,newInterval.end );
                     intervals.remove(startIndex+1);
                     intervals.set(startIndex, startInterval);
                }
                else
                {
                     endInterval.start = newInterval.start;
                     if(endInterval.end<newInterval.end)
                     {
                         endInterval.end = newInterval.end;
                     }
                     intervals.set(startIndex +1, endInterval);
                }
    
             }
             return intervals;
         }
    
    
         private int binarySearch(List<Interval> intervals, int key)
         {
            int mid = intervals.size()/2;
            return rBinarySearch(intervals,mid, intervals.size()-1, 0, key);
         }
    
         private int rBinarySearch(List<Interval> intervals, int mid, int end, int start, int key)
         {
            Interval current = intervals.get(mid);
            if(current.start == key )
            {
                return mid;
            }
            else if(current.start>key)
            {
                end = mid;
                mid = end-((mid-start)/2);
                if(end-start <= 1)
                {
                    {
                        Interval startInterval = intervals.get(start);
                        if(startInterval.start>key)
                        {
                            return (start-1);
                        }
                        else
                        {
                            return start;
                        }
                    }
    
                }
               return rBinarySearch(intervals,  mid,  end,  start, key);
            }
            else
            {
                start = mid;
                mid = ((end-mid)/2)+ start;
               
                if(end-start <=1)
                {
                          Interval endInterval = intervals.get(end);
                          if(endInterval.start <= key )
                          {
                        	 
                              return end;
                          }
    
                          else
                          {
                              return start;
                          }
                }
                
               return rBinarySearch( intervals,  mid,  end,  start, key);
            }
    
    
         }
    
    }

Log in to reply
 

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