The wind tunnel diary

A university wind tunnel takes one booking at a time, and every request carries a fee. Fitting in the most runs and earning the most money turn out to be different problems.

The problem

Each request is a triple [start, end, fee]: the hour the run begins, the hour it ends, and what the customer pays. Hours run from the start of the week.

A run is all-or-nothing: accept the whole booking or refuse it. Two runs may touch: one ending at hour 12 leaves the tunnel free for one starting at 12. Report the largest total fee from a set of requests that never puts two runs in the tunnel at once.

Input. runs — a list of [start, end, fee] triples, in any order.

Output. The largest total fee from a set of non-overlapping runs.

Example.

runs = [[9, 12, 60], [10, 13, 40], [12, 16, 90], [13, 17, 30]]   ->  150

Accept 9–12 and 12–16 for 60 + 90. Taking 10–13 instead rules out the 90 and caps the week at 70.

A second example, where taking more runs earns less:

runs = [[8, 9, 10], [9, 10, 10], [8, 10, 100]]   ->  100

The two short runs fit back to back inside the long run's hours and pay a fifth as much between them.

Constraints.

• 1 <= len(runs) <= 5 * 10^4
• 0 <= start < end <= 10^9
• 1 <= fee <= 10^4

Hints

Approach

Brute force

Enumerate every subset, discard those with an overlap, keep the richest: 2ⁿ subsets, a trillion at 40 requests, and the diary may hold 50,000.

The insight

Sort by end hour, and the best answer over the first k requests depends on one earlier answer: the best over the runs finished by this run's start.

The exchange argument behind earliest-finish-first counts bookings, and collapses once bookings pay different amounts: swapping in the run that frees the tunnel soonest can swap out the fee. What survives is weaker and still enough. Sorted by end hour, the requests compatible with run k form a prefix, so their best total is one table entry rather than a search. That prefix property is the precondition, and only this sort gives it.

Algorithm

1. Sort runs by end hour and keep ends, the sorted end hours.
2. Hold a table where best[k] is the most money from the first k runs, with best[0] = 0.
3. For run k with (start, end, fee), binary search ends for the count j of runs ending at or before start.
4. best[k + 1] = max(best[k], fee + best[j]) — leave it, or take it on top of the richest compatible prefix.
5. The answer is the table's last entry.

Complexity

Time O(n log n) — the sort dominates, and each step does one binary search. Space O(n) for the table and the end hours.

Solution

"""The wind tunnel diary — weighted interval scheduling over sorted end hours."""
from bisect import bisect_right


def solve(runs):
    order = sorted(runs, key=lambda run: run[1])
    ends = [run[1] for run in order]
    # best[k] = the most money earnable using only the first k runs of `order`
    best = [0] * (len(order) + 1)
    for k, (start, _end, fee) in enumerate(order):
        # runs ending at or before `start` are a prefix, because the list is
        # sorted by end hour; bisect_right keeps the run that ends exactly at it
        compatible = bisect_right(ends, start)
        best[k + 1] = max(best[k], fee + best[compatible])
    return best[-1]

TESTS = [
    (([[9, 12, 60], [10, 13, 40], [12, 16, 90], [13, 17, 30]],), 150),
    (([[8, 9, 10], [9, 10, 10], [8, 10, 100]],), 100),
    (([[0, 5, 10], [0, 2, 6], [2, 5, 6]],), 12),
    (([[3, 7, 25]],), 25),
    (([[1, 4, 5], [2, 5, 7], [3, 6, 4]],), 7),
    (([[0, 1, 4], [1, 2, 4], [2, 3, 4], [0, 3, 10]],), 12),
]

Pitfalls

• Sorting by start hour. Compatible requests stop being a prefix, so best[j] quietly includes a run overlapping the one being added, and the total comes out too high.
• Searching the end hours with a left-biased bisect. A run ending exactly at s is compatible with one starting at s; a left bisect drops that fee and turns the first example into 90.
• Taking the highest fee first. On [[0, 5, 10], [0, 2, 6], [2, 5, 6]] the fat 10 blocks both sixes and the week earns 10 instead of 12.

Variants

• The single enlarger — the same intervals with the fees stripped out, where the greedy sort is optimal.
• The exchange argument — the proof that works there, and the exact step that fails here.