0057-insert-interval.py

"""
57. Insert Interval

Submitted: March 15, 2026

Runtime: 0 ms (beats 100.00%)
Memory: 21.57 MB (beats 16.82%)
"""

# this solution inserts the interval and then re-merges the whole array
# can make more efficient by only re-merging w/ two adjacent elements.

import bisect

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        if not intervals:
            return [newInterval]

        i = bisect.insort_left(intervals, newInterval)

        return self.merge(intervals)

    # copied from 56 sol

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()

        res = []
        for (start, end) in intervals:
            if not res:
                res.append((start, end))
                continue
            prev = res[-1]
            prev_start, prev_end = prev
            if prev_end >= start:
                start = min(start, prev_start)
                end = max(end, prev_end)
                res[-1] = (start, end)
            else:
                res.append((start, end))

        return res