Dasher Daily Pay from Order Events with Double Rate in Peak Windows

A Dasher (a delivery driver) is paid for the time spent delivering orders. You are given the order events for one Dasher's day. At any moment, the active orders are those that have been accepted and not yet delivered. Pay accrues per minute: while k orders are active, the Dasher earns k * base_rate cents per minute. During peak time, that rate is doubled.

Return the Dasher's total pay for the day, in cents. An empty peak_windows list gives the base version without peak time.

Function Signature

def dasher_pay(events: list[tuple[int, str, str]], base_rate: int, peak_windows: list[tuple[int, int]]) -> int:

Rules

• Each event is (time, order_id, kind). time is in whole minutes since the start of the day, and kind is "accept" or "deliver".
• An order is active during the half-open interval [accept_time, deliver_time). An order whose accept and deliver times are equal is never active and earns nothing.
• Each peak window (start, end) covers the half-open interval [start, end). Peak windows never overlap each other, but they may touch (one window's end equals another's start), and they are given in any order.
• The minute [m, m + 1) earns active(m) * base_rate cents, where active(m) is the number of orders active during that minute. If the minute lies inside a peak window, it earns twice that amount. The answer is the sum over every minute of the day.
• A peak window that starts or ends in the middle of an active period splits that period: only the part inside the window is paid at the double rate.
• A minute with no active order earns nothing, whether or not it is inside a peak window.
• Return the exact total as an integer number of cents.

Constraints

• 0 <= len(events) <= 200000. Every order_id appears exactly twice, once with "accept" and once with "deliver", and its accept time is less than or equal to its deliver time.
• events is sorted by time in non-decreasing order. Events with equal times may appear in any order.
• 0 <= time <= 1440
• Each order_id is a non-empty string of at most 20 lowercase letters and digits.
• 1 <= base_rate <= 1000
• 0 <= len(peak_windows) <= 1440, and 0 <= start < end <= 1440 for every window.
• There are at most 100,000 orders, so the result is at most 100000 * 1440 * 2 * 1000, which is 2.88 * 10^11. That exceeds 2^31 - 1, so use a 64-bit integer; it stays below 2^53.

Examples

Example 1

Input:  events = [(0, "a", "accept"), (10, "b", "accept"), (20, "a", "deliver"), (30, "b", "deliver")]
        base_rate = 10
        peak_windows = []
Output: 400

Minutes 0 to 9 have one active order (100 cents), minutes 10 to 19 have two (200 cents), and minutes 20 to 29 have one (100 cents).

Example 2

Input:  events = [(0, "a", "accept"), (10, "b", "accept"), (20, "a", "deliver"), (30, "b", "deliver")]
        base_rate = 10
        peak_windows = [(15, 25)]
Output: 550

Minutes 0 to 9: 1 order at the normal rate, 100 cents. Minutes 10 to 14: 2 orders at the normal rate, 100 cents. Minutes 15 to 19: 2 orders at the double rate, 200 cents. Minutes 20 to 24: 1 order at the double rate, 100 cents. Minutes 25 to 29: 1 order at the normal rate, 50 cents.

Example 3

Input:  events = [(100, "x", "accept"), (130, "x", "deliver"), (200, "y", "accept"), (200, "y", "deliver")]
        base_rate = 3
        peak_windows = [(110, 120), (90, 110)]
Output: 150

Order x is active in minutes 100 to 129. Minutes 100 to 119 fall inside the two touching peak windows and earn 20 * 3 * 2 = 120 cents, and minutes 120 to 129 earn 10 * 3 = 30 cents. Order y is never active. Minutes 90 to 99 are peak time with no active order, so they earn nothing.

Dasher Pay with Doubled Peak-Time Minutes

Hints

1. The total is defined as a sum over the minutes of the day: for each minute you only need how many orders are active and whether that minute is peak time.
2. Both orders and windows are half-open: an order delivered at minute t is not active during minute t, and a window (start, end) does not contain minute end.
3. Events that share a timestamp may be listed in any order, so do not assume an accept is listed before the matching deliver when their times are equal.

Approach

Pay is defined minute by minute, so the answer is the sum over m in [0, T) with T = 1440 of active(m) * base_rate, doubled when minute m lies inside a peak window. Build two difference arrays over the T + 1 time points of the day. For every event add +1 at its time for an accept and -1 at its time for a deliver. The prefix sum at minute m then equals (accepts at or before m) minus (delivers at or before m). Because every order's accept time is at most its deliver time, an order contributes 1 to that difference exactly when accept_time <= m < deliver_time, so the prefix sum is active(m). Pairing events by order_id is therefore unnecessary, and events that share a timestamp net out in the same slot whatever order they are listed in; a zero-length order, even one whose deliver is listed before its accept, contributes +1 and -1 to the same slot and is never active. For every window add +1 at start and -1 at end. Windows never overlap, so this prefix sum is 1 on minutes inside some window and 0 elsewhere; where two windows touch, the -1 of one and the +1 of the next cancel at the seam, so no minute is counted twice. Sweep m from 0 to T - 1, maintain both prefix sums, and add active * base_rate, times 2 when the peak prefix sum is positive. A minute with no active order adds nothing even inside a peak window. The half-open rules hold automatically: an order delivered at t stops counting before minute t, and a window (start, end) does not include minute end, so an order delivered at a window start or accepted at a window end earns no peak minute. Accumulate in a 64-bit integer because the total can reach 2.88 * 10^11, which exceeds 2^31 - 1 but stays below 2^53. Edge cases: empty events return 0 regardless of the windows; an empty peak_windows list gives the base version; times 0 and 1440 are valid boundaries, and minute 1439 is the last minute that can earn.

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