insert_interval.py

from typing import List


class Solution:
    """LeetCode #57 - Insert Interval (Medium)
    https://leetcode.com/problems/insert-interval/

    `intervals` is already sorted by start and non-overlapping. Insert
    `newInterval`, merging whatever it collides with, and keep the result sorted
    and non-overlapping.
    """

    def insert(
        self,
        intervals: List[List[int]],
        newInterval: List[int],
    ) -> List[List[int]]:
        """Three phases: before, overlapping, after - one pass, no sorting.

        Key insight: the input is already sorted, so the intervals split into
        exactly three consecutive groups. Sorting again (as in #56) would throw
        away that guarantee and cost O(n log n) for nothing.

          1. entirely before  -> ends before the new one starts: copy as is;
          2. overlapping      -> starts at or before the new one ends: absorb it
                                 by widening the running [start, end];
          3. entirely after   -> copy the rest.

        The overlap test is the part to get right. Two intervals touch when
        `a.start <= b.end and b.start <= a.end`; phase 1 has already ruled out
        everything failing the first half, so `intervals[i][0] <= end` is all
        that remains to check. Note `<=`, not `<`: [1,3] and [3,5] share the
        point 3 and must merge into [1,5].

        Time:  O(n) - each interval is looked at once.
        Space: O(n) - the output.
        """
        result = []
        start, end = newInterval
        i, n = 0, len(intervals)

        # 1. Everything that finishes before the new interval begins.
        while i < n and intervals[i][1] < start:
            result.append(intervals[i])
            i += 1

        # 2. Everything that touches it - widen instead of appending.
        while i < n and intervals[i][0] <= end:
            start = min(start, intervals[i][0])
            end = max(end, intervals[i][1])
            i += 1
        result.append([start, end])

        # 3. The untouched tail.
        while i < n:
            result.append(intervals[i])
            i += 1

        return result