# 7+ lines, 3 easy solutions

• Solution 1: (7 lines, 88 ms)

Collect the intervals strictly left or right of the new interval, then merge the new one with the middle ones (if any) before inserting it between left and right ones.

``````def insert(self, intervals, newInterval):
s, e = newInterval.start, newInterval.end
left = [i for i in intervals if i.end < s]
right = [i for i in intervals if i.start > e]
if left + right != intervals:
s = min(s, intervals[len(left)].start)
e = max(e, intervals[~len(right)].end)
return left + [Interval(s, e)] + right
``````

Solution 2: (8 lines, 84 ms)

Same algorithm as solution 1, but different implementation with only one pass and explicitly collecting the to-be-merged intervals.

``````def insert(self, intervals, newInterval):
s, e = newInterval.start, newInterval.end
parts = merge, left, right = [], [], []
for i in intervals:
parts[(i.end < s) - (i.start > e)].append(i)
if merge:
s = min(s, merge[0].start)
e = max(e, merge[-1].end)
return left + [Interval(s, e)] + right
``````

Solution 3: (11 lines, 80 ms)

Same again, but collect and merge while going over the intervals once.

``````def insert(self, intervals, newInterval):
s, e = newInterval.start, newInterval.end
left, right = [], []
for i in intervals:
if i.end < s:
left += i,
elif i.start > e:
right += i,
else:
s = min(s, i.start)
e = max(e, i.end)
return left + [Interval(s, e)] + right``````

• It is always a pleasure to read your Python codes. :-) The `parts[(i.end < s) - (i.start > e)].append(i)` in Solution 2 is damn clever!

• Yeah, I like that one a lot. Came up with it a while back and I'm happy every time I can use it :-)

• Great solutions! I always learn something new about Python when I read your code. So smart!

• I wrote my own solution earlier but looking at your solution, it makes it much easier to read/understand the code. I think simpler solution is always much better and easier to get it right especially at the time of interview. Thank you very much for sharing your solution.

Here is basically my way of translating your solutions into C++.

``````vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
vector<Interval> left, right;
for (int i = 0; i < intervals.size(); i++) {
if (intervals[i].end < newInterval.start) {
left.push_back(intervals[i]);
}
if (intervals[i].start > newInterval.end) {
right.push_back(intervals[i]);
}
}
int s = newInterval.start, e = newInterval.end;
if ((left.size()+right.size()) != intervals.size()) {
s = min(s, intervals[left.size()].start);
e = max(e, intervals[intervals.size()-right.size()-1].end);
}
Interval middle(s,e);
left.push_back(middle);
left.insert(left.end(), right.begin(), right.end());
return left;
}
``````

• I've learned python 3 years and this is my first time to see syntax like ~9, awesome.

• Very beautiful!

• Thanks for the awesome and clean solutions!

I think in the 3rd solution, it should be `left += [i]` instead of `left += i`? So is that of `right += i`.

• @atomake I'm not doing `left += i`.

• @StefanPochmann My bad. There is a comma. it is `left += i,` then.

May I ask what's such usage called? It does the same as `append()` but I guess there are some performance concerns?

• May I ask what's such usage called?

I don't know whether the usage is called something. What I'm using is the comma operator, and it creates a tuple.

I think sometimes it looks nicer than `append` (thanks to the spaces around `+=`), I think it's slightly faster in one of Python 2 or 3 (can never remember which one), and I want to make people aware of the comma operator :-)

• 4-liner in Python:

``````class Solution(object):
def insert(self, intervals, newInterval):
starts, ends = [x.start for x in intervals], [x.end for x in intervals]
i, j = bisect.bisect_left(ends, newInterval.start), bisect.bisect_right(starts, newInterval.end)
intervals[i:j] = [newInterval] if i==j else [Interval(min(newInterval.start,starts[i]), max(newInterval.end,ends[j-1]))]
return intervals
``````

• @StefanPochmann

Easy to understand Python code below. Add newInterval to the existing intervals and keep merging.

``````    intervals = sorted(intervals+[newInterval], key = lambda x: x.start)
output = [intervals[0]]
for i in xrange(1, len(intervals)):
if intervals[i].start <= output[-1].end:
output[-1] = Interval(output[-1].start, max(intervals[i].end, output[-1].end))
else:
output.append(intervals[i])
return output``````

• very elegant code, a small comment that I have is that you can do this without creating multiple lists and needing to merge them which creates a new list. Here is what I did.
""""
def insert(self, intervals, newInterval):
new_intervals = []
new_begin = newInterval.start
new_end = newInterval.end

``````    last_index = 0
for index in range(len(intervals)):
interval = intervals[index]

if interval.start > new_end:
last_index = index
break

last_index = index + 1
if new_begin <= interval.end:
new_begin = min(interval.start,new_begin)
new_end = max(interval.end, new_end)
else:
new_intervals.append(interval)

new_intervals.append(Interval(new_begin, new_end))
for i in range(last_index,len(intervals)):
new_intervals.append(intervals[i])
return new_intervals
``````

""""""""""
This runs in 65 ms vs 80 ms, a bit faster.

• parts[(i.end < s) - (i.start > e)].append(i)

Magnificent!

• Hi @StefanPochmann