57. Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

  public class Solution {
      public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
          if(intervals.size() ==0 ){
              intervals.add(newInterval);
              return intervals;
          }
          ArrayList<Interval> result = new ArrayList<>();
          int i = 0;
          for(;i<intervals.size();i++){
              Interval cur = intervals.get(i);
              if(cur.end < newInterval.start){
                  result.add(cur);
              }else{
                  break;
              }
          }
          //merge
          for(; i<intervals.size(); i++){
              Interval cur = intervals.get(i);
              if(newInterval.end < cur.start){
                  break;
              }else{
                  newInterval.start = Math.min(newInterval.start, cur.start);
                  newInterval.end = Math.max(newInterval.end, cur.end);
              }
          }
          result.add(newInterval);
          for(;i<intervals.size(); i++){
              result.add(intervals.get(i));
          }

          return result;
      }
  }

 /**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> res = new ArrayList<>();
        if(intervals == null) return res;
        int i =0;
        for(; i< intervals.size(); i++){
            if(newInterval.end < intervals.get(i).start){
                res.add(newInterval);
                break;
            }else if(intervals.get(i).end < newInterval.start){
                res.add(intervals.get(i));
            }else{
                newInterval.start = Math.min(intervals.get(i).start, newInterval.start);
                newInterval.end = Math.max(intervals.get(i).end, newInterval.end);
            }
        }
        if(i == intervals.size()) res.add(newInterval);
        while(i < intervals.size()) res.add(intervals.get(i++));
        return res;
    }
}