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