## # 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 = []
for interval in intervals:
if interval < new_interval:
result.append(interval)
else:
if interval > new_interval: # disjoint
result.append(new_interval)
result.append(interval)
else: # has overlap
result.append([min(interval, new_interval), max(interval, new_interval)])
else:
result[-1] = max(result[-1], interval)
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]
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 > intervals[i])
{
res.push_back(intervals[i]);
}
else if (newInterval < intervals[i])
{
break;
}
else
{
newInterval = std::min(newInterval, intervals[i]);
newInterval = std::max(newInterval, intervals[i]);
}
}
res.push_back(newInterval);
for (; i < intervals.size(); ++i)
{
res.push_back(intervals[i]);
}
return res;
}
};
``````