This took me a long time to cover all cases.

---

Solution

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        start, end = newInterval
        inserted = False
        res = []
        for item in intervals:
            if end < item[0]:
                if not inserted:
                    res.append([start, end])
                    inserted = True
                res.append(item)
            elif end >= item[0] and end <= item[1]:
                start = item[0] if item[0] < start else start
                end = item[1]
            elif start >= item[0] and end <= item[1]:
                start, end = item
                res.append([start, end])
                inserted = True
            elif start >= item[0] and start <= item[1] and end > item[1]:
                start = item[0]
            elif start > item[1]:
                res.append(item)

        if not inserted:
            res.append([start, end])
        return res
            

O(n) = n since we iterate over all elements once.

---

Improvements

This solution has the same complexity, but it is simpler thereby being more maintanable.

class Solution:
    def insert(self, 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(intervals[i][0], newInterval[0])
            newInterval[1] = max(intervals[i][1], newInterval[1])
            i += 1
        
        res.append(newInterval)
        res.extend(intervals[i:])

        return res