Solutions

# Loop throug intervals, and check for overlap. 3 cases: comes before current interval (end is before its start), comes after (start is after its end), or there is some overlap. In the last case, we merge the intervals by taking the minimum of the starts and the maximum of the ends.
# intervals

# O(n) time, O(n) space
def insert(intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
    res = []
    
    for i in range(len(intervals)):
        # Present and all remaining intervals come after newInterval
        if newInterval[1] < intervals[i][0]:
            res.append(newInterval)
            return res + intervals[i:]
        # Present interval comes before and doesn't overlap with newInterval
        elif intervals[i][1] < newInterval[0]:
            res.append(intervals[i])
        # There is some overlap
        else:
            newInterval = [min(newInterval[0], intervals[i][0]),
                            max(newInterval[1], intervals[i][1])]
        
    res.append(newInterval)
    return res


# Linear scan approach: O(n) time, O(n) space
def insert1(intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
    res = []
    n = len(intervals)

    i = 0
    while i < n and intervals[i][1] < newInterval[0]:
        res.append(intervals[i])
        i += 1 

    while i < n and newInterval[1] >= intervals[i][0]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1
    res.append(newInterval)

    while i < n:
        res.append(intervals[i])
        i += 1

    return res