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.
Community answers
Answer by rmeda188
from collections import defaultdict
def dasher_pay(events, base_rate, peak_windows):
deliveries = defaultdict(list)
for time, order_id, kind in events:
deliveries[order_id].append(time)
total = 0
for order_id in deliveries:
start, end = deliveries[order_id]
# Base pay
total += (end - start) * base_rate
# Extra pay for peak minutes (double rate)
for peak_start, peak_end in peak_windows:
overlap = max(
0,
min(end, peak_end) - max(start, peak_start)
)
total += overlap * base_rate
return total
Answer by shahdharmil3103
easy difference array technique to compute ans with prefix sum
#include
using namespace std;
class Solution {
public:
long long dasher_pay(const std::vector>& events, int base_rate, const std::vector>& peak_windows) {
long long ans = 0;
vectordif(1450,0);
vectorpdif(1450,0);
set st;
for(auto i : events){
int t = get<0>(i);
string type = get<2>(i);
string o = get<1>(i);
if(type == "accept"){
st.insert(o);
dif[t]++;
}else{
st.erase(o);
dif[t]--;
}
}
for(int i=1;i<1450;i++){
dif[i] += dif[i-1];
}
for(auto i : peak_windows){
pdif[i[0]]++;
pdif[i[1]]--;
}
for(int i=1;i<1450;i++){
pdif[i] += pdif[i-1];
}
for(int i=0;i<1450;i++){
int ac = dif[i];
int p = pdif[i];
if(p > 0){
ans += 2 1LL ac * base_rate;
}else{
ans += 1LL ac base_rate;
}
}
return ans;
}
};