Modified based on the neat O(n) solution of Stefan.

```
# Definition for an interval.
# class Interval(object):
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class Solution(object):
def insert(self, intervals, newInterval):
# log(n)
# find the largest index that interval i.end < s
def binarySearch1(intervals, s, l, r):
ret = -1
while l<=r:
mid = l+r >>1
if intervals[mid].end < s:
ret = mid
l=mid+1
else:
r=mid-1
return ret
# smallest i such that i.start > e
def binarySearch2(intervals, e, l, r):
ret = -1
while l<=r:
mid = l+r >>1
if intervals[mid].start > e:
ret = mid
r=mid-1
else:
l=mid+1
return ret
s = newInterval.start
e = newInterval.end
left = intervals[:binarySearch1(intervals, s, 0, len(intervals)-1)+1]
index_right = binarySearch2(intervals, e, 0, len(intervals)-1)
right = intervals[index_right:] if index_right != -1 else []
if len(left) + len(right) != len(intervals):
# megre
s = min(intervals[len(left)].start, s)
e = max(intervals[~len(right)].end, e)
return left + [Interval(s,e)] + right
```