Insert Interval leetcode

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

遍历整个interval组, 

如果cur.end > 给出interval.start 说明要merge的区间在后面 当前的interval可以入列

如果 cur.start > interval.end 说明merge去边在前边 注意这时候不是当前cur入列 而是interval入列 并且让当前的cur = interval

如果cur跟interval有重叠 只更新interval的范围 不入列

注意因为遍历完成之后1. interval的范围比较大 还没入列

2. interval已经入列了但是cur还没入列  但是此intval的值 = cur 

所以循环之后都要把interval入列 

因为遍历一遍 所以时间O(n)

public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> res = new ArrayList<Interval>();
        for (Interval cur : intervals) {
            if (cur.start > newInterval.end) {
                res.add(newInterval);
                newInterval = cur;
            } else if (cur.end < newInterval.start) {
                res.add(cur);
            } else if (cur.start < newInterval.end || cur.end > newInterval.start) {
                newInterval.start = Math.min(cur.start, newInterval.start);
                newInterval.end = Math.max(cur.end, newInterval.end);
            }
        }
        res.add(newInterval);
        return res;
    }
}