Just scan the intervals, and make sure whether the newInterval or intervals[i] should be considered to be merged, once the newInterval is merged, you don't want to consider it again, so make it's "start" very large.
Some corner cases:
- Empty given list
- newInteral never been merged even after the iteration of the intervals
Here is an elegant way to solve this: append a very large interval at the end of the intervals, and don't forget to get rid of it when returning.
class Solution(object): def insert(self, intervals, newInterval): i, ans = 0,  intervals.append(Interval(0xffffffff, 0xffffffff)) while i < len(intervals): if intervals[i].start < newInterval.start: interval = intervals[i] else: interval, newInterval.start, i = Interval(newInterval.start, newInterval.end), 0xffffffff + 1, i - 1 if not ans or interval.start > ans[-1].end: ans.append(interval) else: ans[-1].end = max(ans[-1].end, interval.end) i += 1 return ans[:-1]