The single enlarger

A community darkroom has one enlarger and a wall of requests for it. The order they came in says nothing; the hour each one clears the bench says everything.

The problem

Each request is a pair [start, clear]: the hour a member wants the negative under the lamp, and the hour the bench is clear again. Hours run from the start of term. The enlarger takes one negative at a time, and a session may begin in the hour another clears: [9, 11] and [11, 13] can both be booked, [9, 11] and [10, 14] cannot.

A request is all or nothing: take the whole session or turn it down. Members pay per session, not per hour, so the darkroom books as many as it can. Report that number.

Input. sessions — a list of [start, clear] pairs, in no particular order.

Output. The most sessions bookable without two negatives on the enlarger at once.

Example.

sessions = [[13, 16], [9, 11], [10, 14], [16, 20], [11, 13], [18, 22]]   ->  4

Book 9–11, 11–13, 13–16 and 16–20. Nothing left starts at hour 20 or later, so four is the ceiling.

A second example, where taking the request that starts first is a mistake:

sessions = [[8, 19], [9, 12], [13, 17]]   ->  2

The 8–19 request holds the bench for eleven hours and counts as one. Turning it down books the two shorter requests instead, and counts as two.

Constraints.

• 0 <= len(sessions) <= 10^5
• 0 <= start < clear <= 10^9
• requests may repeat, and overlap in any pattern

Hints

Approach

Brute force

Enumerate every subset and keep the largest with no overlapping pair: 2ⁿ subsets, each costing a scan — hopeless past about 25 requests, and the wall may hold 100,000.

The insight

Among the requests that still fit, the one clearing the bench earliest belongs to some optimal timetable, so it can be booked without a second thought.

Take an optimal timetable, let X be its first session and G the earliest-clearing request that fits. G clears no later than X, so putting G in place of X clashes with nothing booked after X: the timetable keeps its size and now agrees with the greedy choice. Repeat on the rest and greedy matches an optimal timetable down the list. The precondition: "does it fit" turns on one number, the hour the bench is next free — true only because there is one enlarger.

Algorithm

1. Sort the requests by clearing hour.
2. Hold free, the first hour the bench is available, unset to begin with.
3. Walk the sorted list. If start >= free, book it, add one to the count, and set free to its clearing hour.
4. Otherwise skip it.
5. Return the count.

Complexity

Time O(n log n) — the sort dominates; the walk touches each request once. Space O(n) for the sorted copy, or O(1) if you sort in place.

Solution

"""The single enlarger — activity selection by earliest finishing time."""


def solve(sessions):
    booked = 0
    free = None                            # the first hour the bench is clear
    for start, clear in sorted(sessions, key=lambda s: s[1]):
        # invariant: `booked` sessions fit in the hours before `free`, and no
        # timetable over the sessions seen so far can beat that count
        if free is None or start >= free:
            booked += 1
            free = clear
    return booked

TESTS = [
    (([[13, 16], [9, 11], [10, 14], [16, 20], [11, 13], [18, 22]],), 4),
    (([[8, 19], [9, 12], [13, 17]],), 2),
    (([[10, 18], [16, 20], [18, 26]],), 2),
    (([],), 0),
    (([[12, 21]],), 1),
    (([[7, 8], [8, 9], [9, 10]],), 3),
    (([[14, 15], [14, 15], [14, 15]],), 1),
]

Pitfalls

• Sorting by starting hour. The second example then books 8–19 first and returns 1. Wanting the bench early says nothing about clearing it early.
• Sorting by length. On [[10, 18], [16, 20], [18, 26]] the shortest request is 16–20, and booking it clashes with both others, so the count is 1 and not 2.
• Testing start > free instead of start >= free. A negative may go under the lamp in the hour another clears, and the strict test turns the first example into 3.
• Seeding free from the first request. An empty wall is allowed, and sorted(sessions)[0] raises an IndexError where the answer is 0.

Variants

• The wind tunnel diary — attach a fee to each interval and this greedy stops being optimal.
• The exchange argument — the swap used above, written out as a general proof technique.