Dasher Pay from Concurrent Orders with Double-Pay Time 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 they spend carrying orders, and the pay grows with the number of orders they carry at once. During any minute, the Dasher earns `base_rate` multiplied by the number of orders in progress during that minute.
Some periods are double-pay windows: during any minute inside one, the pay for that minute is doubled. The windows were added in the second part of the question; the first part is the same computation with no windows.
Given the base rate, the Dasher's orders and the double-pay windows, return the Dasher's total pay.
### Function Signature
```python
def dasher_pay(base_rate: int, orders: list[list[int]], double_pay_windows: list[list[int]]) -> int:
```
`orders[i] = [accepted_at, delivered_at]` means the Dasher accepted order `i` at minute `accepted_at` and delivered it at minute `delivered_at`. `double_pay_windows[j] = [start, end]` describes one double-pay window. All times are whole minutes on one shared timeline, and all pay is in cents.
### Rules
- Order `i` is in progress during every minute `m` with `accepted_at <= m < delivered_at`; the minute in which it is delivered does not count.
- A window covers every minute `m` with `start <= m < end`.
- Let `c(m)` be the number of orders in progress during minute `m`. Minute `m` pays `base_rate * c(m)` if no window covers it, and `2 * base_rate * c(m)` if a window covers it. A minute with no order in progress pays nothing.
- Return the total pay over all minutes, in cents. With no orders, return 0.
- Orders may overlap one another in any way, and an order may start or end inside a window.
### Constraints
- `1 <= base_rate <= 1000`
- `0 <= len(orders) <= 10^5`, and `0 <= accepted_at < delivered_at <= 10^6` for every order
- `0 <= len(double_pay_windows) <= 10^5`, and `0 <= start < end <= 10^6` for every window
- No two windows overlap, although one window may end at the minute where another starts. Neither the orders nor the windows are given in any particular order.
- The answer can reach `2 * 10^14`, which exceeds `2^31 - 1`; use 64-bit integers in languages with fixed-width integer types. It stays below `2^53`.
### Examples
**Example 1**
```text
Input: base_rate = 10, orders = [[0, 30], [10, 40]], double_pay_windows = []
Output: 600
```
Minutes 0 through 9 have one order in progress: 10 minutes × 1 × 10 = 100. Minutes 10 through 29 have two: 20 × 2 × 10 = 400. Minutes 30 through 39 have one: 10 × 1 × 10 = 100. The total is 600.
**Example 2**
```text
Input: base_rate = 10, orders = [[0, 30], [10, 40]], double_pay_windows = [[20, 35]]
Output: 850
```
Minutes 0 through 9: one order, not doubled, 100. Minutes 10 through 19: two orders, not doubled, 200. Minutes 20 through 29: two orders, doubled, 400. Minutes 30 through 34: one order, doubled, 100. Minutes 35 through 39: one order, not doubled, 50. The total is 850.
**Example 3**
```text
Input: base_rate = 3, orders = [[5, 10], [10, 12]], double_pay_windows = [[10, 11], [0, 5]]
Output: 24
```
The first order covers minutes 5 through 9, which no window covers, so it pays 5 × 3 = 15; it touches both windows but overlaps neither. The second order covers minutes 10 and 11: minute 10 lies inside the window `[10, 11]` and pays 2 × 3 = 6, and minute 11 pays 3. The total is 24.
Overview: Compute a Dasher's total pay when every minute pays a base rate times the number of orders in progress, and minutes inside double-pay windows pay twice as much. Tests reasoning about overlapping intervals, exact half-open time boundaries, and computing large totals efficiently for many orders and windows.
A Dasher (a delivery driver) is paid for the time they spend carrying orders, and the pay grows with the number of orders they carry at once. During any minute, the Dasher earns `base_rate` multiplied by the number of orders in progress during that minute.
Some periods are double-pay windows: during any minute inside one, the pay for that minute is doubled. (In the original interview the windows were the second part of the question; the first part is the same computation with no windows, which here is `double_pay_windows = []`.)
Given the base rate, the Dasher's orders and the double-pay windows, return the Dasher's total pay.
Implement `dasher_pay(base_rate, orders, double_pay_windows)`. `orders[i] = [accepted_at, delivered_at]` means the Dasher accepted order `i` at minute `accepted_at` and delivered it at minute `delivered_at`. `double_pay_windows[j] = [start, end]` describes one double-pay window. All times are whole minutes on one shared timeline, and all pay is in cents.
### Rules
- Order `i` is in progress during every minute `m` with `accepted_at <= m < delivered_at`; the minute in which it is delivered does not count.
- A window covers every minute `m` with `start <= m < end`.
- Let `c(m)` be the number of orders in progress during minute `m`. Minute `m` pays `base_rate * c(m)` if no window covers it, and `2 * base_rate * c(m)` if a window covers it. A minute with no order in progress pays nothing.
- Return the total pay over all minutes, in cents, as an integer. With no orders, return 0.
- Orders may overlap one another in any way, and an order may start or end inside a window.
### Constraints
- `1 <= base_rate <= 1000`
- `0 <= len(orders) <= 10^5`, and `0 <= accepted_at < delivered_at <= 10^6` for every order
- `0 <= len(double_pay_windows) <= 10^5`, and `0 <= start < end <= 10^6` for every window
- No two windows overlap, although one window may end at the minute where another starts. Neither the orders nor the windows are given in any particular order.
- The answer can reach `2 * 10^14`, which exceeds `2^31 - 1`: Java returns `long` and C++ returns `long long`. It stays below `2^53`.
### Example 1
```text
Input: base_rate = 10, orders = [[0, 30], [10, 40]], double_pay_windows = [[20, 35]]
Output: 850
```
Minutes 0 through 9: one order, not doubled, 100. Minutes 10 through 19: two orders, not doubled, 200. Minutes 20 through 29: two orders, doubled, 400. Minutes 30 through 34: one order, doubled, 100. Minutes 35 through 39: one order, not doubled, 50. The total is 850.
### Example 2
```text
Input: base_rate = 3, orders = [[5, 10], [10, 12]], double_pay_windows = [[10, 11], [0, 5]]
Output: 24
```
The first order covers minutes 5 through 9, which no window covers, so it pays 5 × 3 = 15; it touches both windows but overlaps neither. The second order covers minutes 10 and 11: minute 10 lies inside the window `[10, 11]` and pays 2 × 3 = 6, and minute 11 pays 3. The total is 24.
Constraints
- 1 <= base_rate <= 1000
- 0 <= len(orders) <= 10^5, and 0 <= accepted_at < delivered_at <= 10^6 for every order
- 0 <= len(double_pay_windows) <= 10^5, and 0 <= start < end <= 10^6 for every window
- No two windows overlap, although one window may end at the minute where another starts. Neither the orders nor the windows are given in any particular order.
- The answer can reach 2 * 10^14, which exceeds 2^31 - 1 (Java returns long, C++ returns long long); it stays below 2^53.
Examples
Input: (1, [], [])
Expected Output: 0
Explanation: Minimum valid input: no orders and no windows pay 0.
Input: (500, [], [[0, 10], [20, 30]])
Expected Output: 0
Explanation: No orders: windows alone pay nothing.
Hints
- Both kinds of interval are half-open: the minute equal to delivered_at or to end is excluded, so an order that ends exactly where a window starts earns no doubled minute.
- The pay for a minute depends only on how many orders are in progress and whether a window covers it, and both can change only at an order or window endpoint. With up to 10^5 orders over 10^6 minutes, avoid visiting every minute once per order.
- The total can reach 2 * 10^14, so accumulate it in a 64-bit integer.