57. Insert Interval

https://leetcode.com/problems/insert-interval/

Python

• Time: O(n)
• Space: O(n+1)

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        if len(intervals) < 1:
            return intervals + [newInterval]

        result = []
        start, end = newInterval

        for interval in intervals:
            if interval[1] < start or interval[0] > end:
                result.append(interval)
                continue

            start = min(interval[0], start)
            end = max(interval[1], end)
        result.append([start, end])

        # TODO: should able to finish without sort
        result.sort(key=lambda pair: pair[0])

        return result