public List<Interval> insert(List<Interval> intervals,Interval newInterval){
  List<Interval> res=new ArrayList<>();
  res.add(newInterval);
  if (intervals == null || intervals.size() == 0) {
    return res;
  }
  for (  Interval i : intervals) {
    int start=res.get(res.size() - 1).start;
    int end=res.get(res.size() - 1).end;
    if (i.end < start) {
      res.add(res.size() - 1,i);
    }
 else     if (end < i.start) {
      res.add(i);
    }
 else {
      start=Math.min(start,i.start);
      end=Math.max(end,i.end);
      res.set(res.size() - 1,new Interval(start,end));
    }
  }
  return res;
}

public List < Interval > insert ( List < Interval > intervals , Interval newInterval ) { List < Interval > res = new ArrayList < > ( ) ; res . add ( newInterval ) ; if ( intervals == null || intervals . size ( ) == 0 ) { return res ; } for ( Interval i : intervals ) { int start = res . get ( res . size ( ) - 1 ) . start ; int end = res . get ( res . size ( ) - 1 ) . end ; if ( i . end < start ) { res . add ( res . size ( ) - 1 , i ) ; } else if ( end < i . start ) { res . add ( i ) ; } else { start = Math . min ( start , i . start ) ; end = Math . max ( end , i . end ) ; res . set ( res . size ( ) - 1 , new Interval ( start , end ) ) ; } } return res ; }
array , sort . o ( n ) . not in place solution , make use of intervals are sorted . go through the given intervals . for each of them , there are 3 situations : 1 ) no overlap , in front of the new interval 2 ) no overlap , behind the new interval 3 ) overlap , merge with the new interval
