Roadworks calendar

The highways depot keeps one calendar of closures for a stretch of road. A new works order arrives, and the calendar has to absorb it without ever listing two closures that overlap.

The problem

The calendar is a list of closure windows, each [from, to] in hours since the start of the month. It arrives sorted by from, and no two windows overlap or touch — the depot keeps it that way so the public notice reads as one line per closure.

A new works order comes in as a single window. Fold it into the calendar and return the calendar in the same form: sorted, with no two windows overlapping or touching. Windows that meet end to end are one continuous closure and must be printed as one window, because the crew stays on site through the boundary and two notices for one closure is what the depot is trying to avoid.

Input. closures — a list of [from, to] integer pairs, sorted ascending by from, pairwise disjoint and non-touching. request — one [from, to] pair with from < to.

Output. The calendar after the insertion, in the same form.

Example.

closures = [[0, 60], [180, 240], [420, 480]], request = [50, 200]
->  [[0, 240], [420, 480]]

The request runs from hour 50 to hour 200, so it swallows the first two windows: 0–60 and 180–240 both meet it, and the three become one closure from 0 to 240. The 420–480 window is untouched.

A second example, where the request only touches:

closures = [[0, 60], [180, 240]], request = [60, 120]
->  [[0, 120], [180, 240]]

The request starts at exactly hour 60, the moment the first window ends, so the crew never leaves and the two become one closure 0–120. The second window opens an hour after the request shuts and stays separate.

Constraints.

• 0 <= len(closures) <= 10^4
• 0 <= from < to <= 10^6
• closures is sorted and disjoint on entry

Hints

Approach

Brute force

Append the request, sort the whole list by from, then sweep merging any pair that overlaps or touches. That is O(n log n) for 10⁴ windows, and it throws away what you were handed: the calendar was already in order, and the sort re-derives that order from nothing.

The insight

The calendar is sorted and disjoint, so the windows the request meets form one contiguous run, and that whole run collapses into a single window.

Everything ending before the request starts is untouched, and everything starting after it ends is untouched, so the answer is prefix, one merged window, suffix. The middle run is contiguous because the windows are sorted by from and never overlap: the first window with from > to_of_request proves that every window after it also starts too late. One pass, no sort.

Algorithm

1. Copy windows while to < request_from — they close before the request opens.
2. While the next window's from <= request_to, absorb it: widen the request to the min of the froms and the max of the tos.
3. Append the widened request.
4. Copy the rest of the calendar unchanged.

Complexity

Time O(n) — every window is looked at once. Space O(n) for the returned calendar; the algorithm itself holds two integers.

Solution

"""Roadworks calendar — three phases over an already sorted closure calendar."""


def solve(closures, request):
    lo, hi = request
    merged = []
    i, n = 0, len(closures)

    # Phase 1: windows that shut before the request opens are untouched.
    while i < n and closures[i][1] < lo:
        merged.append(closures[i])
        i += 1

    # Phase 2: every window from here that starts at or before hi meets the
    # request, so it collapses into one widening window. The calendar is sorted
    # and disjoint, so these windows are contiguous — once one fails the test,
    # none after it can pass.
    while i < n and closures[i][0] <= hi:
        lo = min(lo, closures[i][0])
        hi = max(hi, closures[i][1])
        i += 1
    merged.append([lo, hi])

    # Phase 3: the tail opens after the request shuts.
    merged.extend(closures[i:])
    return merged

TESTS = [
    (([[0, 60], [180, 240], [420, 480]], [50, 200]), [[0, 240], [420, 480]]),
    (([[0, 60], [180, 240]], [60, 120]), [[0, 120], [180, 240]]),
    (([[0, 300]], [100, 200]), [[0, 300]]),
    (([], [90, 150]), [[90, 150]]),
    (([[0, 60], [180, 240]], [300, 360]), [[0, 60], [180, 240], [300, 360]]),
    (([[100, 200], [300, 400], [500, 600]], [0, 700]), [[0, 700]]),
    (([[100, 200]], [0, 50]), [[0, 50], [100, 200]]),
]

Pitfalls

• Using closures[i][0] < hi in phase two leaves touching windows apart: the second example returns [[0, 60], [60, 120], [180, 240]] and the depot posts two notices for one closure.
• Assigning hi = request[1] rather than max(hi, closures[i][1]) loses the tail of a window that swallows the request. Inserting [100, 200] into [[0, 300]] then yields [[0, 200]], reopening a road that is still shut.
• Forgetting the request that lands after everything — if the loop ends without appending the widened window, request = [300, 360] vanishes from the calendar.
• Binary-searching a single insertion point and splicing the request in puts it in the right place and leaves every overlap: inserting [0, 700] into [[100, 200], [300, 400], [500, 600]] returns four overlapping windows where the answer is one.

Variants

• Rehearsal room clashes — the same sorted intervals, choosing which to drop instead of merging.
• Spectrum licence ledger — this insertion run thousands of times, plus removal and coverage queries.