**Solution**

**Insert Interval** https://leetcode.com/problems/insert-interval/

**Algorithm**

- First merge the newInterval with the existing sorted list. Use the standard code to merge two sorted lists.
- Then simply run the algorithm to merge a sorted interval list. https://discuss.leetcode.com/topic/75108/python-solution-with-detailed-explanation

```
class Solution(object):
def merge(self, intervals):
result = [intervals[0]]
for i in range(1, len(intervals)):
i1, i2 = result[-1], intervals[i]
if i2.start > i1.end:
result.append(i2)
elif i2.end >= i1.end:
i1.end = i2.end
return result
def insert(self, intervals, newInterval):
"""
:type intervals: List[Interval]
:type newInterval: Interval
:rtype: List[Interval]
"""
result = []
l1, l2 = intervals, [newInterval]
i, j = 0, 0
while i < len(l1) or j < len(l2):
if i == len(l1):
result.append(l2[j])
j += 1
elif j == len(l2):
result.append(l1[i])
i += 1
elif l1[i].start <= l2[j].start:
result.append(l1[i])
i += 1
else:
result.append(l2[j])
j += 1
return self.merge(result)
```