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].

思路1：建立新的结果返回，遍历原来的线段组（注意原来是按照start排序之后的），所以根据是否和新的interval重叠，加入新的结果中（结果也要求按start排序）。

public class Solution {    public ArrayList
    
      insert(ArrayList
     
       intervals, Interval newInterval) {        if (newInterval == null)            return intervals;        ArrayList
      
        res = new ArrayList
       
        ();        for (Interval each : intervals) {            if (each.end < newInterval.start)                res.add(each);            else if (each.start > newInterval.end) {                res.add(newInterval);                newInterval = each;            } else {                newInterval = new Interval(Math.min(each.start, newInterval.start), Math.max(each.end, newInterval.end));            }        }        res.add(newInterval);        return res;    }    public static void main(String[] args) {        // Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as        Interval one = new Interval(1, 2);        Interval two = new Interval(3, 5);        Interval three = new Interval(6, 7);        Interval four = new Interval(8, 10);        Interval five = new Interval(12, 16);        ArrayList
        
          intervals = new ArrayList
         
          (); intervals.add(one); intervals.add(two); intervals.add(three); intervals.add(four); intervals.add(five); System.out.println(new Solution().insert(intervals, new Interval(4, 9))); }}
         
        
       
      
     
    

参考：