[LeetCode]Insert Interval

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

本题难度Hard。

【复杂度】
时间 O(N) 空间 O(N)

【思路】
这道题目与​​[LeetCode]Merge Intervals​​很像，不过这里有个前提你得看到：​​intervals​​​已经根据其​​start​​进行过排序，所以就不用再进行排序了（实际上不排序照样能做出来）。我们只要对三种情况进行处理：

1、间隔在newInterval之前（不重叠）。放入before
2、间隔在newInterval之后（不重叠）。放入after
3、间隔与newInterval重叠。重叠操作

然后把​​before、newInterval、after​​​放入​​ans​​即可。

【注意】
返回的​​​ans​​​要求是按​​start​​排序的。

【附】
把​​​before、after​​​放入​​ans​​​可以使用方法​​addAll​​。

【代码】

public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        //require
        if(newInterval==null)
            return intervals;
        List<Interval> ans=new LinkedList<Interval>(),before=new LinkedList<Interval>(),after=new LinkedList<Interval>();
        //invariant
        for(Interval i:intervals){
            if(newInterval.end<i.start)
                after.add(i);
            else if(i.end<newInterval.start)
                before.add(i);
            else{
                newInterval.start=Math.min(i.start,newInterval.start);
                newInterval.end=Math.max(i.end,newInterval.end);
            }
        }
        ans.addAll(before);
        ans.add(newInterval);
        ans.addAll(after);
        //ensure
        return ans;
    }
}