57. Insert Interval

Problem:

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:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Analysis:
一开始想到的是排序的方法。先把newInterval插入intervals，然后整体排序。这道题就变成了，merge intvertal了。然而效率是悲惨的，因为排序是O(nlogn)。

最好的解法是一次性遍历时间复杂度是O(n)。分3个部分。
1. 在newInterval之前没有和newInterval 重叠的:cur.end < newInterval.start
2. 所有和newInterval重叠的： cur.end >= newInterval.start && cur.start <= newInterval.end
3. 在newInterval之后没有和它重叠的： cur.start > newInterval.end

Solution:
有2个极端情况需要考虑。
1. intervals不为空但是size为0，[], 那么直接返回newInterval.
2. intervals size为1，和newInterval 重叠，最后需要再double check。
第二个corner case不容易想出来，感觉是这道题最难得地方。

class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> res = new ArrayList<>();
        if (intervals == null)
            return res;
        if (intervals.size() == 0) {
            res.add(newInterval);
            return res;
        }
        int start = newInterval.start, end = newInterval.end;
        boolean merged = false;
        for (int i = 0; i < intervals.size(); i++) {
            Interval cur = intervals.get(i);
            if (cur.end < newInterval.start) {
                res.add(cur);
            } else if (cur.end >= newInterval.start && cur.start <= newInterval.end) {
                start = Math.min(start, cur.start);
                end = Math.max(end, cur.end);
            } else if (cur.start > newInterval.end) {
                if (!merged) {
                    res.add(new Interval(start, end));
                    merged = true;
                }
                res.add(cur);
            }
        }
        
        if (!merged) {
            res.add(new Interval(start, end));
        }
        return res;
    }
}