Irrigation windows

A field controller holds one opening per zone, and the zones share a pump. What the pump sees is not the list of openings but the stretches of the day during which at least one valve is open.

The problem

Each irrigation zone is programmed with a window: the minute the valve opens and the minute it closes, measured from midnight. The windows arrive in whatever order the zones were programmed, and they overlap freely — two zones may share a window exactly, one may sit entirely inside another, and one may end at the very minute the next begins.

Collapse the list into the runs of continuous flow. Two windows belong to the same run if they overlap, and also if they merely touch: a valve closing at minute 120 while another opens at 120 leaves the pump running without a break. Return the runs in increasing order of start time; no two of them may touch, or they would be one run.

Input. windows — a list of [open, close] pairs of integers, minutes from midnight, with open <= close. The list may be empty.

Output. A list of [open, close] pairs, sorted by opening minute, covering exactly the minutes when the pump runs.

Example.

windows = [[300, 380], [360, 420], [500, 540], [415, 460]]
  ->  [[300, 460], [500, 540]]

Sorted by start, three of them chain: 300–380 overlaps 360–420, and 415 falls inside that, extending the run to 460. The 500–540 window starts after the run ends, so it stands alone.

A second example, with a window swallowed by an earlier one and a pair that only touches:

windows = [[60, 120], [120, 150], [30, 200], [400, 400]]
  ->  [[30, 200], [400, 400]]

30–200 covers both of the first two windows entirely, and the zero-length window at 400 survives as its own run.

Constraints.

• 0 <= len(windows) <= 10^5
• 0 <= open <= close <= 1440
• Windows arrive in no particular order.

Hints

Approach

Brute force

Repeatedly scan every pair of windows, merge the first overlapping pair, and start again. Each merge costs O(n²) comparisons and there can be n − 1 of them, so this is O(n³) — a hundred thousand windows is out of the question.

The insight

Sort by opening minute and every merge becomes local: the next window either extends the one run you are holding or opens a new one, and no earlier run can ever be revisited.

The precondition is the sort. After it, every remaining window opens at or after the current window's opening minute, so if a window does not touch the run you hold, no later window can reach that run either — later windows open even further right. That is what turns a quadratic search for pairs into one pass.

Algorithm

1. If the list is empty, return an empty list.
2. Sort the windows by opening minute.
3. Hold the first window as the current run.
4. For each following window: if it opens at or before the run's closing minute, set the run's close to the larger of the two closes; otherwise emit the run and hold the new window.
5. Emit the run you are still holding.

Complexity

Time O(n log n) — the sort dominates; the sweep is one pass. Space O(n) for the output, or O(log n) beyond it if you sort in place.

Minutes here are bounded by 1440, so a counting sort by opening minute replaces the comparison sort and makes the whole thing O(n + 1440). That trade wins while the range stays close to the number of windows and stops winning the moment timestamps become seconds since an epoch.

Solution

"""Irrigation windows — sort by opening minute, then merge in one sweep."""


def solve(windows):
    if not windows:
        return []
    ordered = sorted(windows)              # by opening minute, close as tiebreak
    runs = [list(ordered[0])]
    for start, end in ordered[1:]:
        # invariant: runs[-1] is the only run the sort allows this window to
        # touch, because every later window opens at or after `start`.
        if start <= runs[-1][1]:
            runs[-1][1] = max(runs[-1][1], end)
        else:
            runs.append([start, end])
    return runs

TESTS = [
    (([[300, 380], [360, 420], [500, 540], [415, 460]],), [[300, 460], [500, 540]]),
    (([[60, 120], [120, 150], [30, 200], [400, 400]],), [[30, 200], [400, 400]]),
    (([],), []),
    (([[480, 495]],), [[480, 495]]),
    (([[0, 1440], [700, 700], [30, 90]],), [[0, 1440]]),
    (([[10, 20], [21, 30], [31, 40]],), [[10, 20], [21, 30], [31, 40]]),
]

Pitfalls

• Sorting by closing minute. On [[0, 100], [10, 20], [30, 40]] the sweep holds 10–20, emits it, then merges 0–100 into 30–100 — two runs that between them lose the minutes 0 to 10.
• Assigning the new window's close instead of the larger close. A swallowed window such as 20–40 inside 30–200 shortens the run to 30–40 and loses 160 minutes of flow.
• Testing overlap with a strict <. Windows 60–120 and 120–150 come back as two runs even though the pump never stopped, and the output then contains two runs that touch — which the statement forbids.

Variants

• Kiln slots — the same sorted sweep, but it counts how many windows are open at once instead of merging them.
• Lane bookings — the overlap question answered after every insertion, not once at the end.