A laundromat has k identical washing machines and one line at the door. Customers are listed in the order they arrive: loads[i] = (arrival, minutes, patience).
Customers are handled strictly in list order. Customer i looks at the machine that becomes free earliest; they'd start at start = max(arrival, that machine's free time).
- If they'd have to wait more than
patienceminutes (start - arrival > patience), they walk out: their answer is-1and no machine is used. - Otherwise they take that machine, which is busy until
start + minutes, and their answer is that finish time.
All machines are free at time 0. Write finish_times(k: int, loads: list[tuple[int, int, int]]) -> list[int] that returns each customer's answer, in order.
finish_times(2, [(0, 30, 0), (5, 10, 0), (6, 4, 5), (7, 3, 20), (40, 5, 0)])
# [30, 15, -1, 18, 45]
# customer 0: machine A, 0 -> 30
# customer 1: machine B, 5 -> 15
# customer 2: earliest machine frees at 15, a 9-minute wait > patience 5: leaves (-1)
# customer 3: waits 8 minutes (patience 20), B runs 15 -> 18
# customer 4: arrives at 40, both free: 40 -> 45
1 <= k <= 100,000, up to 200,000 customers,arrivalis non-decreasing down the list,1 <= minutes <= 10**6,0 <= patience. The list may be empty.- A customer who waits exactly
patienceminutes stays. - Looping over all
kmachines for every customer is O(n·k): too slow when both are large. Aim for O(log k) per customer.
Show hint
keep a min-heap of the machines' free times. Start it as [0] * k; the top heap[0] is the earliest free time, so peek at it to decide, and only if the customer stays replace it with the new finish time (heapq.heapreplace pops and pushes in one step).