Dasher Daily Pay from Order Events with Double Rate in Peak Windows
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
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**
```text
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.
Overview: A coding problem that computes a delivery driver's daily pay from accept and deliver events, where the per-minute rate scales with the number of orders in progress. Peak windows double the rate, so active periods that cross a window boundary must be split exactly, and the total is returned in integer cents.
A Dasher (a delivery driver) is paid for the time spent delivering orders. You are given the order events for one Dasher's day, a base rate `base_rate` in cents, and a list of peak-time windows. 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.
Implement `dasher_pay(events, base_rate, peak_windows)` and return the Dasher's total pay for the day, in cents. An empty `peak_windows` list gives the base version without peak time.
### 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. The total can exceed `2^31 - 1`, so accumulate it in a 64-bit integer (`long` in Java, `long long` in C++). It always stays below `2^53`, so a JavaScript number holds it exactly.
### Input format
`events` is a single list of `(time, order_id, kind)` triples: an array of `[time, order_id, kind]` arrays in JavaScript, a `java.util.List<java.util.List<Object>>` whose entries hold an integer time and two strings in Java, and a `std::vector<std::tuple<int, std::string, std::string>>` in C++. `peak_windows` is a list of `(start, end)` pairs: `int[][]` in Java and `std::vector<std::vector<int>>` in C++.
### Example 1
```text
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. With `peak_windows = []` the same events earn 400 cents.
### Example 2
```text
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.
### 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`.
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
- kind is "accept" or "deliver".
- 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.
- Peak windows never overlap each other, but they may touch, and they are given in any order.
- 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 (long in Java, long long in C++); it stays below 2^53.
Examples
Input: ([(0, 'a', 'accept'), (10, 'b', 'accept'), (20, 'a', 'deliver'), (30, 'b', 'deliver')], 10, [])
Expected Output: 400
Explanation: Source example 1, base version: 10 + 20 + 10 order-minutes at 10 cents each.
Input: ([(0, 'a', 'accept'), (10, 'b', 'accept'), (20, 'a', 'deliver'), (30, 'b', 'deliver')], 10, [(15, 25)])
Expected Output: 550
Explanation: Source example 2: the window [15, 25) starts inside a's period and starts and ends inside b's period; 40 base order-minutes plus 15 doubled extras, times 10.
Hints
- 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.
- 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.
- 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.