Telescope night

The dome holds one telescope and tonight's requests arrived in whatever order the astronomers filed them. Either every window fits, or two of them want the mirror at the same minute.

The problem

An observatory books a single telescope. Each request is a window [start, end], in minutes after sunset: the astronomer needs the mirror from start up to but not including end. The dome swings and refocuses in seconds, so a window ending at 120 and a window starting at 120 are both honourable — they touch, they do not overlap.

The night coordinator wants one answer before working through the queue: can every request be honoured exactly as filed? Nothing is dropped, shortened or moved, so if any two windows claim a common minute the night is infeasible.

Filing order is not observing order, and that is the whole difficulty. A clash can sit between the first request and the last, and a short window can be buried inside a long one, so looking at neighbours in the list as filed settles nothing.

Input. windows — a list of [start, end] integer pairs with start < end, in filing order.

Output. True if no two windows overlap, False otherwise.

Example.

windows = [[30, 75], [130, 190], [80, 125]]   ->  True

In time order the windows run 30–75, 80–125 and 130–190. Each ends before the next begins, with five minutes to spare each time.

A second example, where the clash is between requests filed far apart:

windows = [[0, 45], [200, 260], [40, 90]]   ->  False

The third request starts at 40 and the first runs to 45, so five minutes are claimed twice. Filing order hides the pair; time order puts them next to each other. Touching windows are still fine: [[10, 60], [60, 110]] is True.

Constraints.

• 0 <= len(windows) <= 10^4
• 0 <= start < end <= 10^6
• an empty list is a valid night, and the answer for it is True

Hints

Approach

Brute force

Test every pair with the overlap condition: n(n − 1)/2 tests, about 50 million at n = 10,000, nearly all of them on windows hours apart. The test itself is worth keeping — a_start < b_end and b_start < a_end is true exactly when two windows share a minute, nested pairs included. What is wrong is not the test but that it is asked about pairs that could have been ruled out for free.

The insight

Sort by start time and only neighbours can clash: if window i ends before window i+1 begins, it ends before every later window begins, because the starts are non-decreasing.

Sorting is what supplies the precondition — after it, start[i+1] <= start[j] for every j beyond i+1. So a single test, end[i] <= start[i+1], retires all n − i − 1 pairs involving window i at once. That is how a linear scan comes to cover a quadratic number of pairs, and it is the reason the sort is not bookkeeping but the actual algorithm.

Equal starts need no special case: both windows have positive length, so whichever the sort puts first ends strictly past the other's start and the same test rejects the pair. Nesting needs none either — a window inside another starts later, so it is the next neighbour.

Algorithm

1. Sort the windows by start time.
2. Walk the adjacent pairs in that order.
3. If a window's end is strictly greater than the next window's start, return False.
4. If the walk finishes, return True.

Complexity

Time O(n log n) — the sort dominates, and the scan is one pass of n − 1 comparisons. Space O(n) for the sorted copy, or O(1) beyond the sort itself if reordering the caller's list is allowed.

Solution

"""Telescope night — sort the windows by start, then only neighbours can clash."""


def solve(windows):
    order = sorted(windows, key=lambda w: w[0])
    # Sorted by start, every window after `later` starts at or after later[0],
    # so this one comparison rules out all of them, not just the next pair.
    for earlier, later in zip(order, order[1:]):
        if earlier[1] > later[0]:      # touching (end == start) is allowed
            return False
    return True

TESTS = [
    (([[30, 75], [130, 190], [80, 125]],), True),
    (([[0, 45], [200, 260], [40, 90]],), False),
    (([[10, 60], [60, 110]],), True),      # back-to-back windows are feasible
    (([],), True),                          # no requests is a valid night
    (([[0, 1000000]],), True),
    (([[100, 150], [0, 50]],), True),       # feasible but filed out of order
    (([[0, 300], [100, 120]],), False),     # a short window nested inside a long one
    (([[5, 25], [5, 25]],), False),         # identical windows always clash
]

Pitfalls

• Testing end >= next_start. Back-to-back windows like [10, 60] and [60, 110] are legal, and >= rejects them: a workable night comes back False.
• Scanning without sorting. [[100, 150], [0, 50]] has adjacent entries whose first end, 150, exceeds the second start, 0, so an unsorted scan answers False on a night with no clash at all.
• Reading windows[0] before checking for an empty list. A night with no requests is feasible and must answer True; an eager first read raises IndexError instead.
• Returning True from inside the loop. A return True in the else branch ends the scan after one pair: [[0, 10], [20, 30], [25, 40]] answers True on the strength of its first gap and never looks at the clash behind it.

Variants

• Village hall chargers — the same overlap arithmetic, but two simultaneous windows are allowed and only a third is refused.
• Trailhead campsites — sorting to impose an order the caller asked for, rather than to expose adjacency.