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

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);
}

}

}``````

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