Given a non-overlapping interval list which is sorted by start point. Insert a new interval into it, make sure the list is still in order and non-overlapping (merge intervals if necessary).

Example

Insert `[2, 5]`

into `[[1,2], [5,9]]`

, we get `[[1,9]]`

.

Insert `[3, 4]`

into `[[1,2], [5,9]]`

, we get `[[1,2], [3,4], [5,9]]`

.

class Solution {
/**
* Insert newInterval into intervals.
* @param intervals: Sorted interval list.
* @param newInterval: A new interval.
* @return: A new sorted interval list.
*/
public ArrayList < Interval > insert ( ArrayList < Interval > intervals , Interval newInterval ) {
//If the list of intervals is empty, we just have to add the new
//interval and return
if ( intervals . isEmpty ()) {
intervals . add ( newInterval );
return intervals ;
}
//Insert position
int insert = - 1 ;
//Left and right used for binary search
int left = 0 ;
int right = intervals . size () - 1 ;
//Use binary search to find insert position
while ( left <= right ) {
int mid = ( right - left ) / 2 + left ;
Interval midInterval = intervals . get ( mid );
if ( newInterval . start == midInterval . start ) {
insert = mid ;
break ;
}
//Break before left becomes larger than right, or vice versa, so left
//pointer can be use at the next step
if ( left == right )
break ;
if ( newInterval . start < midInterval . start ) {
right = mid - 1 ;
}
else {
left = mid + 1 ;
}
}
//If overlapping interval found
if ( insert != - 1 ) {
intervals . get ( insert ). end = Math . max ( intervals . get ( insert ). end , newInterval . end );
}
else {
if ( intervals . get ( left ). start < newInterval . start ) {
intervals . add ( left + 1 , newInterval );
insert = left + 1 ;
}
else {
intervals . add ( left , newInterval );
insert = left ;
}
}
//Check to see if new interval overlap with previous interval
if ( insert > 0 && intervals . get ( insert ). start <= intervals . get ( insert - 1 ). end ) {
intervals . get ( insert - 1 ). end = Math . max ( intervals . get ( insert - 1 ). end , intervals . get ( insert ). end );
insert --;
}
//Check to merge following intervals.
while ( true ) {
if ( insert == intervals . size () - 1 )
break ;
//If overlap
if ( intervals . get ( insert ). end >= intervals . get ( insert + 1 ). start ) {
intervals . get ( insert ). end = Math . max ( intervals . get ( insert ). end , intervals . get ( insert + 1 ). end );
intervals . remove ( insert + 1 );
}
else
break ;
}
return intervals ;
}
}

public classs Interval {
int start , end ;
Interval ( int start , int end ) {
this . start = start ;
this . end = end ;
}
}