# 57. Insert Interval

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

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

# Solution

Approach 1: iteration. Time O(N).

Approach 2: sort intervals + newInterval, then check each one and merge if needed. Time O(NlogN).

# Code (Python)

Approach 1:

    def insert(self, intervals: List[List[int]], new_interval: List[int]) -> List[List[int]]:
        # O(N)
        # possibilities: disjoint(left, right, middle), overlap -- keep an added flag
        result = []
        added = False
        for interval in intervals:
            if interval[1] < new_interval[0]:
                result.append(interval)
            else:
                if interval[0] > new_interval[1]: # disjoint
                    if not added:
                        result.append(new_interval)
                        added = True
                    result.append(interval)
                else: # has overlap
                    if not added:
                        result.append([min(interval[0], new_interval[0]), max(interval[1], new_interval[1])])
                        added = True
                    else:
                        result[-1][1] = max(result[-1][1], interval[1])
        if not added:
            result.append(new_interval)
        return result

or:

    def insert(self, intervals, newInterval):
        # O(N): https://leetcode.com/discuss/42018/7-lines-3-easy-solutions
        if not intervals:
            return [newInterval]
        before, after = [], []
        s, e = newInterval.start, newInterval.end
        for interval in intervals:
            if interval.end < newInterval.start:
                before.append(interval)
            elif interval.start > newInterval.end:
                after.append(interval)
            else:
                s = min(s, interval.start)
                e = max(e, interval.end)
        return before + [Interval(s, e)] + after

Approach 2:

    def insert(self, intervals, newInterval):
        # O(NlogN): http://www.cnblogs.com/zuoyuan/p/3782048.html
        # idea: sort intervals + newInterval, then check each one and merge if needed
        intervals.append(newInterval)
        intervals.sort(key = lambda x:x.start)
        res=[intervals[0]]
        for i in range(1, len(intervals)):
            if res[-1].start <= intervals[i].start <= res[-1].end:
                res[-1].end = max(intervals[i].end, res[-1].end)
            else:
                res.append(intervals[i])
        return res

# Code (C++)

Approach 1:

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int i = 0;
        for (; i < intervals.size(); ++i)
        {
            if (newInterval[0] > intervals[i][1])
            {
                res.push_back(intervals[i]);
            }
            else if (newInterval[1] < intervals[i][0])
            {
                break;
            }
            else
            {
                newInterval[0] = std::min(newInterval[0], intervals[i][0]);
                newInterval[1] = std::max(newInterval[1], intervals[i][1]);
            }
        }
        res.push_back(newInterval);
        for (; i < intervals.size(); ++i)
        {
            res.push_back(intervals[i]);
        }
        return res;
    }
};