Python short and clean. Binary Search.
Approach\n1. Use bisect_left() to binary search the index si such that all intervals below si end before the start of new_interval.\n\n2. Use bisect_right() to 
# Approach\n1. Use `bisect_left()` to binary search the index `si` such that all intervals below `si` end before the start of `new_interval`.\n\n2. Use `bisect_right()` to binary search the index `ei` such that all intervals above `ei` start after the end of `new_interval`.\n\n3. Merge all intervals between `si` and `ei`, by finding the minimum `start` and maximum `end` points. \n\n4. Insert the merged interval `[start, end]` and return.\n\n\n# Complexity\n- Time complexity: $$O(n)$$, counting the returned list.\n\n- Space complexity: $$O(1)$$, not counting the returned list.\n\nwhere, `n is the number of intervals`\n\n# Code\n```python\nclass Solution:\n    def insert(self, intervals: list[list[int]], new_interval: list[int]) -> list[list[int]]:\n        si = bisect.bisect_left( intervals, new_interval[0], key=lambda x: x[1])\n        ei = bisect.bisect_right(intervals, new_interval[1], key=lambda x: x[0])\n        \n        start = min(intervals[si][0], new_interval[0]) if si < len(intervals) else new_interval[0]\n        end = max(intervals[ei - 1][1], new_interval[1]) if ei > 0 else new_interval[1]\n\n        return intervals[:si] + [[start, end]] + intervals[ei:]\n\n```
['Binary Search', 'Python', 'Python3']