# O(n) Python solution

• ``````class Solution:
# @param intervals, a list of Intervals
# @param newInterval, a Interval
# @return a list of Interval
def insert(self, intervals, newInterval):
start = newInterval.start
end = newInterval.end
result = []
i = 0
while i < len(intervals):
if start <= intervals[i].end:
if end < intervals[i].start:
break
start = min(start, intervals[i].start)
end = max(end, intervals[i].end)
else:
result.append(intervals[i])
i += 1
result.append(Interval(start, end))
result += intervals[i:]
return result``````

• Great idea! I made a little modification to make it in-place.

``````class Solution:
def insert(self, intervals, newInterval):
start = newInterval.start
end = newInterval.end
right = left = 0
while right < len(intervals):
if start <= intervals[right].end:
if end < intervals[right].start:
break
start = min(start, intervals[right].start)
end = max(end, intervals[right].end)
else:
left += 1
right += 1
return intervals[:left] + [Interval(start, end)] + intervals[right:]``````

• ``````class Solution:

def merge(self, intervals):
intervals.sort(lambda a,b: a.end - b.end)
intervals.sort(lambda a,b: a.start - b.start)
i, n = 0, len(intervals)
result = []
while i < n:
s = i
j = i + 1
maxEnd = intervals[i].end
while j < n and maxEnd >= intervals[j].start:
maxEnd = max(maxEnd, intervals[j].end)
i += 1
j += 1
result.append(Interval(intervals[s].start, maxEnd))
i = j
return result

def insert(self, intervals, newInterval):
"""
:type intervals: List[Interval]
:type newInterval: Interval
:rtype: List[Interval]
"""
intervals.append(newInterval)
return self.merge(intervals)``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.