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]

此题比较难，首先，intervals是排好序的，所以不需要小顶堆来排序了。这道题可以起个名字叫做隔离法，首先，与newInterval不接触的链表里面的Interval全部都排除出去，接下来剩下接触的Interval了，这个时候，将链表里面的Interval和newInterval一个一个进行比较，start取两者的较小值，end取两者的较大值。此题就做完了。当然了，说是排除出去其实是将Interval放进res里面去的。代码如下：

/**

 * 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<Interval>();

        int i=0;

        while(i<intervals.size()&&intervals.get(i).end<newInterval.start){

            res.add(intervals.get(i++));

        }

        while(i<intervals.size()&&intervals.get(i).start<=newInterval.end){

            newInterval.start = Math.min(intervals.get(i).start,newInterval.start);

            newInterval.end = Math.max(intervals.get(i).end,newInterval.end);

            i++;

        }

        res.add(new Interval(newInterval.start,newInterval.end));

        while(i<intervals.size()) res.add(intervals.get(i++));

        return res;

    }

}

57. Insert Interval