Village hall chargers

The car park has a row of charge posts and one small transformer behind them. Two cars drawing at the same minute is fine; a third trips the breaker, so a booking that would create one is refused when it is made.

The problem

The hall books its charge posts by the minute. A booking is a window [start, end]: the car draws current from start up to but not including end, so a booking ending at 120 and one starting at 120 never share a minute.

The transformer carries two cars at once. A third at any single minute trips the breaker and all three stop, so the clerk applies one rule — a request is accepted only if, together with everything already accepted, no minute carries three cars drawing. A refused request is dropped: it never runs, and it must not affect any later decision. Requests are decided one at a time, in arrival order.

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

Output. A list of booleans the same length, True where the request was accepted.

Example.

requests = [[60, 120], [90, 150], [100, 110], [120, 180]]
->  [True, True, False, True]

The first two are accepted and overlap on 90–120: two cars, which is fine. The third sits inside that stretch and would be a third car there, so it is refused. The fourth starts at 120, where the doubled stretch ends, so it never shares a minute with both earlier bookings.

A second example, where a long window covers a short one without ever being third:

requests = [[10, 20], [50, 60], [10, 40], [5, 15]]
->  [True, True, True, False]

[10, 40] overlaps one accepted window, so it is accepted and 10–20 becomes doubled. [5, 15] then reaches into 10–15, already doubled, and is refused.

Constraints.

• 1 <= len(requests) <= 1000
• 0 <= start < end <= 10^9 — the minutes are far too sparse to mark a timeline
• decisions are made in arrival order, and a refused request leaves no trace

Hints

Approach

Brute force

For each request, take every pair of accepted windows and ask whether all three share a minute. That is a three-way intersection test over O(m²) pairs per request and O(n³) across the day — a billion tests at n = 1000, on top of code that has to get a three-way intersection right.

The insight

Keep a second log of the stretches already covered twice; then "would this be a third car" is an ordinary two-way overlap test against that log, and accepting a window means adding its overlaps with the accepted log to it.

Any minute covered three times is covered twice by two of the three, so it is already in the doubles log and the three-way question never has to be asked. The precondition is that the two logs describe exactly the accepted set, which is why a refused request must not be written anywhere.

The doubles log also stays short: two doubled stretches can never overlap, since a minute inside both would carry three accepted windows and that state was refused before it could exist.

Algorithm

1. Keep accepted and doubled, both starting empty.
2. For each request [s, e], compare it with every entry [ds, de] in doubled: they overlap when max(s, ds) < min(e, de).
3. If any overlaps, record False and change nothing else.
4. Otherwise, for every [a, b] in accepted that overlaps, append the shared stretch [max(s, a), min(e, b)] to doubled.
5. Append [s, e] to accepted and record True.

Complexity

Time O(n²) — each request scans two logs, and both stay O(n) long, the doubles log because its entries are pairwise disjoint. Space O(n) for the two logs.

Solution

"""Village hall chargers — an accepted log plus a log of doubled stretches."""


def shared(a_start, a_end, b_start, b_end):
    """The stretch two half-open windows have in common, or None if they only touch."""
    start, end = max(a_start, b_start), min(a_end, b_end)
    return (start, end) if start < end else None


def solve(requests):
    accepted, doubled, answers = [], [], []
    for start, end in requests:
        # A third car at some minute means two accepted bookings already cover it,
        # so the doubled log turns the three-way question into a two-way test.
        if any(shared(start, end, ds, de) is not None for ds, de in doubled):
            answers.append(False)
            continue                       # a refused window leaves no trace at all
        for a_start, a_end in accepted:
            piece = shared(start, end, a_start, a_end)
            if piece is not None:
                doubled.append(piece)
        accepted.append((start, end))
        answers.append(True)
    return answers

TESTS = [
    (([[60, 120], [90, 150], [100, 110], [120, 180]],), [True, True, False, True]),
    (([[10, 20], [50, 60], [10, 40], [5, 15]],), [True, True, True, False]),
    # A refused window must not be recorded: [45, 90] never happened.
    (([[0, 50], [25, 75], [45, 90], [80, 100], [85, 95]],), [True, True, False, True, True]),
    # Touching two accepted windows is not the same as being third at one minute.
    (([[0, 10], [90, 100], [0, 100]],), [True, True, True]),
    (([[5, 15]],), [True]),
    (([[0, 10], [10, 20], [20, 30]],), [True, True, True]),
    (([[0, 1000000000], [0, 1000000000], [0, 1000000000]],), [True, True, False]),
]

Pitfalls

• Testing overlap with <=. max(s, ds) <= min(e, de) counts a shared endpoint as an overlap, so the fourth request of the first example, starting exactly where the doubled stretch ends, is refused: [True, True, False, False].
• Recording a refused window. Forgetting to stop after writing False leaves the request in accepted, and a later window overlapping only that ghost invents a doubled stretch. On [[0, 50], [25, 75], [45, 90], [80, 100], [85, 95]] the last request is then refused, though its only real company is one accepted booking.
• Counting how many accepted windows a request touches. Touching two is not the same as being third at one minute: after [0, 10] and [90, 100], the window [0, 100] meets both and must still be accepted, because it is never with the two of them at once.

Variants

• Telescope night — the same overlap arithmetic where the limit is one booking instead of two, and the whole list is known in advance.
• Consecutive van runs — another decision that must be right the first time, with no chance to undo it.