My brain is too small to figure out all the corner conditions. So I decide to move to reduction solution without optimization. Surprisedly, it is the fastest python solution so far.

```
class Solution:
# @param intervals, a list of Intervals
# @param newInterval, a Interval
# @return a list of Interval
def insert(self, intervals, newInterval):
intervals.append(newInterval)
for i in range(0, len(intervals)- 1):
if intervals[i].start > intervals[-1].start:
intervals[i], intervals[-1] = intervals[-1], intervals[i]
result = [intervals[0]]
for i in range(1, len(intervals)):
if intervals[i].start <= result[-1].end:
result[-1].end = max(result[-1].end, intervals[i].end)
else:
result.append(intervals[i])
return result
```