Binary search. Simple and clear solution
\nclass Solution:\n    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:\n\n        i_left = bisect_left(intervals, newIn
```\nclass Solution:\n    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:\n\n        i_left = bisect_left(intervals, newInterval[0], key= itemgetter(0))\n        i_right = bisect_right(intervals, newInterval[1], key= itemgetter(1))\n\n        if i_left == 0 or newInterval[0] > intervals[i_left-1][1]:\n            start = newInterval[0]\n        else:\n            start = intervals[i_left-1][0]\n            i_left -= 1\n            \n        if i_right == len(intervals) or newInterval[1] < intervals[i_right][0]:\n            end = newInterval[1]\n        else:\n            end = intervals[i_right][1]\n            i_right += 1\n\n        return intervals[:i_left] + [[start, end]] + intervals[i_right:]\n```
['Binary Search', 'Python3']