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

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

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

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

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.

Courier Pay with Concurrent Orders and Peak Windows

Hints

1. Re-read the half-open rules: the deliver minute is not an active minute, and a window's end minute is not a peak minute.
2. The number of active orders changes only at event minutes, and whether a minute is peak changes only at window boundaries.
3. Both lists already arrive sorted by time, so you can advance through them together instead of sorting or visiting every minute one by one.

Approach

Let P(t) be the number of peak minutes before minute t (minutes 0 to t - 1 that lie in some window), and let W(t) = base_rate * (t + (peak_multiplier - 1) * P(t)) be what one order would earn if it were active in every minute before t. An order active in minutes accept_minute <= m < deliver_minute earns exactly W(deliver_minute) - W(accept_minute), because each of its minutes pays base_rate, plus base_rate * (peak_multiplier - 1) extra when the minute is peak. Summing over orders, the total is the sum of W over deliver events minus the sum of W over accept events, so the accept/deliver pairing by order_id never has to be resolved: each order contributes exactly one accept and one deliver. Because events arrive in non-decreasing minute order and windows arrive sorted and disjoint, P(t) is maintained with a single forward pointer: every window whose end is <= t lies entirely before t and is added to a running sum once, and only the next window can partially cover minutes before t, adding t - start when start < t (every later window starts at or after that window's end, which is > t). The pointer never moves backward, so each window is processed once. Half-open boundaries follow directly: a deliver minute is excluded because W(d) counts only minutes before d, and a window's end minute is excluded because it covers only start <= m < end. Edge cases: an order accepted and delivered in the same minute contributes W(t) - W(t) = 0; an empty peak_windows list makes P(t) = 0, giving the first-step answer base_rate * total order-minutes; peak_multiplier = 1 removes the peak term. Totals reach about 10^14, so Java uses long and C++ long long; every intermediate sum stays below about 10^14 < 2^53, so JavaScript numbers stay exact.

• Time complexity: O(n + w)
• Space complexity: O(1)