# 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;
}
};