Three phases in one pass

When something is inserted or removed, the list splits into before, touching, and after.

The same structure, removing instead of adding

Here is the three-phase shape on a different task: removing a range from a set of intervals. The middle phase now splits intervals rather than merging them.

1def remove_range(intervals, cut_start, cut_end):2    result = []3    for start, end in intervals:4        if end <= cut_start or start >= cut_end:5            result.append([start, end])          # untouched6            continue7        if start < cut_start:8            result.append([start, cut_start])    # keep the left remnant9        if end > cut_end:10            result.append([cut_end, end])        # keep the right remnant11    return result12 13print(remove_range([[1, 5], [8, 12]], 3, 9))14print(remove_range([[1, 10]], 3, 5))

Quick check· 5 min

Which comparison ends the middle phase?

You are inserting a new interval and absorbing everything it touches. Which condition means the current interval should be absorbed rather than copied through?

The current interval starts at or before the growing interval's end, and ends at or after its startThe current interval starts strictly after the growing interval's original startThe current interval's start is less than the new interval's original endThe current interval is fully contained within the new interval

Problem· 22 min

Insert Interval

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

The same structure, removing instead of adding

Here is the three-phase shape on a different task: removing a range from a set of intervals. The middle phase now splits intervals rather than merging them.

1def remove_range(intervals, cut_start, cut_end):2    result = []3    for start, end in intervals:4        if end <= cut_start or start >= cut_end:5            result.append([start, end])          # untouched6            continue7        if start < cut_start:8            result.append([start, cut_start])    # keep the left remnant9        if end > cut_end:10            result.append([cut_end, end])        # keep the right remnant11    return result12 13print(remove_range([[1, 5], [8, 12]], 3, 9))14print(remove_range([[1, 10]], 3, 5))