Simple O(log N) python solution
Intuition\nEasiest way to solve it is just iterate through all intervals and merge them with new interval if required.\nHowever, they already sorted. And next s
# Intuition\nEasiest way to solve it is just iterate through all intervals and merge them with new interval if required.\nHowever, they already sorted. And next second you understand that binary-search approach is worth to try\n\n# Approach\nWe just need to take left intact intervals, right intact intervals and then add new interval between them.\nBoth intervals range can be found by binary search. The only problem is that for the right part upper bound will find next enterval after that one we need. So solve it as easy as it sound, just take pre-right interval.\n\n```\n[s0,e0], [s1,e1], ..., [sL,eL],..., [sR-1,eR-1],[sR,eR],...,[sN,eN]\n                          \u2191              \u2191\n                         [intStart,  intEnd]     \n```\n\n# Complexity\n- Time complexity: $$O(log N)$$\n\n- Space complexity: $$O(N)$$\n\n# Code\n```\nclass Solution:\n    def insert(\n        self, intervals: List[List[int]], newInterval: List[int]\n    ) -> List[List[int]]:\n        n = len(intervals)\n        intStart, intEnd = newInterval\n\n        # find by binary search the index of interval that is ended exactly after intStart\n        posL = bisect_left(intervals, intStart, key=lambda it: it[1])\n        if posL < n and intervals[posL][0] < intStart:\n            intStart = intervals[posL][0] # correct new interval\'s start if merge required\n\n        # find by binary search the index of interval that is started exactly after intEnd\n        posR = bisect_right(intervals, intEnd, key=lambda it: it[0], lo=posL)\n        if posR <= n and posR > 0 and intervals[posR - 1][1] > intEnd:\n            intEnd = intervals[posR - 1][1] # correct new interval\'s end if merge required\n\n        return intervals[:posL] + [[intStart, intEnd]] + intervals[posR:]\n\n```
['Python3']