Courier Pay From Overlapping Deliveries With Peak-Window Multipliers

A delivery courier accepts orders and later delivers them, and may carry several orders at the same time. The courier is paid for every minute each order is active, so a minute spent carrying two orders pays twice as much as a minute spent carrying one. Some periods of the day are peak windows, during which every active order pays a multiplied rate. Given the courier's activity log and the peak windows, compute the courier's total pay. The question comes in two steps. The first step computes the pay with no peak windows. The follow-up adds peak windows; the activity log and the window list both arrive already sorted, and the interviewer does not want either of them sorted again. This function covers both steps: an empty `peak_windows` list is the first step. The pay model in the Rules below is an assumption for this exercise. In an interview, agree the pay rule and the shape of the input with the interviewer before writing code. ### Function Signature ```python def courier_pay(events: list[tuple[int, int, str]], peak_windows: list[tuple[int, int]], base_rate: int, peak_multiplier: int) -> int: ``` Each event is `(order_id, minute, kind)`, where `kind` is `"accept"` or `"deliver"`. Each peak window is `(start, end)`. ### Rules - Time is measured in whole minutes. Minute `m` is the interval from `m` up to, but not including, `m + 1`. - Events are listed in non-decreasing order of `minute`. - Every `order_id` has exactly one `"accept"` event and exactly one `"deliver"` event, and its deliver event appears later in the list than its accept event. The two may share the same minute. - An order is active during every minute `m` with `accept_minute <= m < deliver_minute`. An order accepted and delivered in the same minute is never active and earns nothing. - A peak window `(start, end)` covers every minute `m` with `start <= m < end`. Windows are listed in increasing order of `start`, every window has `start < end`, and windows do not overlap, although a window may begin exactly where the previous one ends. - For each minute `m`, let `active(m)` be the number of orders active during that minute. The courier earns `base_rate * active(m)` for the minute if `m` lies in no peak window, and `base_rate * peak_multiplier * active(m)` if it lies in one. A minute with no active order earns nothing. - Return the total earned over all minutes, as an integer number of cents. ### Constraints - `2 <= len(events) <= 2 * 10^5`, and `len(events)` is even. - `0 <= len(peak_windows) <= 10^5` - `0 <= order_id <= 10^9` - `0 <= minute, start, end <= 10^6` - `1 <= base_rate <= 100` (cents per active order per minute) - `1 <= peak_multiplier <= 10` - The answer can reach about `10^14`, which exceeds `2^31 - 1`, so use 64-bit arithmetic. It always stays below `2^53`. - Both input lists arrive sorted. Aim for `O(n + w)` time for `n` events and `w` peak windows, without sorting either list again. ### Examples **Example 1** ```text Input: events = [(1, 0, "accept"), (2, 5, "accept"), (1, 10, "deliver"), (2, 12, "deliver")], peak_windows = [], base_rate = 3, peak_multiplier = 2 Output: 51 ``` Order 1 is active in minutes 0 to 9 and order 2 in minutes 5 to 11. Minutes 0 to 4 have one active order, minutes 5 to 9 have two, and minutes 10 and 11 have one: 5 + 10 + 2 = 17 order-minutes at 3 cents each, which is 51. **Example 2** ```text Input: events = [(1, 0, "accept"), (2, 5, "accept"), (1, 10, "deliver"), (2, 12, "deliver")], peak_windows = [(8, 11)], base_rate = 3, peak_multiplier = 2 Output: 66 ``` Minutes 8, 9 and 10 are peak minutes. Outside them, minutes 0 to 4 (one order, 5 order-minutes), minutes 5 to 7 (two orders, 6) and minute 11 (one order, 1) give 12 order-minutes at 3 cents, which is 36. Inside them, minutes 8 and 9 (two orders, 4 order-minutes) and minute 10 (one order, 1) give 5 order-minutes at 3 * 2 = 6 cents, which is 30. The total is 66. **Example 3** ```text Input: events = [(7, 2, "accept"), (7, 2, "deliver"), (9, 4, "accept"), (9, 6, "deliver"), (8, 9, "accept"), (8, 12, "deliver")], peak_windows = [(0, 3), (5, 10), (10, 11), (20, 30)], base_rate = 1, peak_multiplier = 3 Output: 11 ``` Order 7 is accepted and delivered in minute 2, so it earns nothing even though minute 2 is a peak minute. Order 9 is active in minute 4 (not peak, 1 cent) and minute 5 (peak, 3 cents). Order 8 is active in minute 9 (inside `(5, 10)`, 3 cents), minute 10 (inside `(10, 11)`, 3 cents) and minute 11 (not peak, 1 cent). The window `(20, 30)` covers no active minute. The total is 1 + 3 + 3 + 3 + 1 = 11.