Calculate Courier Earnings
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Design a function to calculate total courier pay from a set of delivery orders.
Assume time is represented as integer minutes, and intervals are half-open: an order active from minute `start` to minute `end` contributes on `[start, end)`.
### Base version
Each order has:
- `accepted_at`
- `delivered_at`
There is a global `rate` paid per minute.
For any minute in which an order is active, that order earns `rate * k`, where `k` is the number of orders active in that same minute. In other words, if `k` orders overlap during a minute, the total pay contributed by that minute is `k * k * rate`.
Implement a function that returns the total pay across all orders.
The interviewer may ask you to define reasonable input/output structures yourself, explain your chosen data structures, analyze time and space complexity, and write meaningful test cases.
### Follow-up 1
Now each order may also include:
- `arrived_at`
- `picked_up_at`
The interval `[arrived_at, picked_up_at)` is store-wait time. A store-wait minute is paid only for that order itself:
- it must not increase the multiplier for any other order
- other orders must not increase its multiplier
Update the design to support this rule.
### Follow-up 2
During configurable peak-hour intervals, the per-minute rate is doubled.
Explain how you would extend your solution to support this efficiently.
Quick Answer: This question evaluates algorithmic problem-solving with emphasis on temporal interval aggregation, handling overlapping events, and applying conditional rate multipliers under specified business rules.
Part 1: Calculate total courier pay with overlapping delivery intervals
You are given a base pay rate per minute and a list of delivery orders. Each order is active on the half-open interval [accepted_at, delivered_at). If k orders are active during the same minute, then each of those k orders earns rate * k for that minute, so the total pay added by that minute is k * k * rate. Return the total pay across all orders.
Constraints
- 0 <= len(orders) <= 200000
- 0 <= rate <= 10^6
- 0 <= accepted_at <= delivered_at <= 10^9
- Orders use half-open intervals: [start, end)
- The final answer fits in a signed 64-bit integer
Examples
Input: (5, [])
Expected Output: 0
Explanation: No orders means no pay.
Input: (10, [[0, 3]])
Expected Output: 30
Explanation: One order is active for 3 minutes, so pay is 3 * 1^2 * 10 = 30.
Hints
- A minute-by-minute simulation is too slow when timestamps are large.
- The number of active orders changes only at start and end times, so process intervals between sorted event times.
Part 2: Support store-wait intervals that do not affect overlap multipliers
Each order is given as [accepted_at, arrived_at, picked_up_at, delivered_at], with accepted_at <= arrived_at <= picked_up_at <= delivered_at. The full order runs on [accepted_at, delivered_at), but the sub-interval [arrived_at, picked_up_at) is store-wait time. A store-wait minute is paid only for that order itself: it does not increase any other order's overlap multiplier, and other orders do not increase its multiplier. Minutes outside store-wait behave like normal delivery minutes and interact with other normal delivery minutes using the same k * k * rate rule. Return the total pay.
Constraints
- 0 <= len(orders) <= 200000
- 0 <= rate <= 10^6
- 0 <= accepted_at <= arrived_at <= picked_up_at <= delivered_at <= 10^9
- All intervals are half-open
- The final answer fits in a signed 64-bit integer
Examples
Input: (5, [])
Expected Output: 0
Explanation: No orders means no pay.
Input: (10, [[0, 2, 4, 6]])
Expected Output: 60
Explanation: Normal segments are [0,2) and [4,6), and wait is [2,4). All are paid at rate 10 with no overlaps, for 6 total minutes.
Hints
- Split each order into up to three pieces: pre-wait, wait, and post-wait.
- Store-wait pay is isolated, so you can count its contribution separately from the overlapping normal segments.
Part 3: Support doubled per-minute rates during configurable peak-hour intervals
Extend the previous rules. Each order is [accepted_at, arrived_at, picked_up_at, delivered_at], where [arrived_at, picked_up_at) is isolated store-wait time. You are also given peak-hour intervals [start, end). During any minute covered by at least one peak interval, the per-minute rate is doubled. If peak intervals overlap, the rate is still only doubled once, not repeatedly. Return the total pay efficiently.
Constraints
- 0 <= len(orders) <= 200000
- 0 <= len(peak_intervals) <= 200000
- 0 <= rate <= 10^6
- 0 <= accepted_at <= arrived_at <= picked_up_at <= delivered_at <= 10^9
- 0 <= peak_start <= peak_end <= 10^9
- All intervals are half-open
- If multiple peak intervals overlap, the rate is doubled once for covered minutes
- The final answer fits in a signed 64-bit integer
Examples
Input: (5, [], [[0, 10]])
Expected Output: 0
Explanation: Peak hours do not matter if there are no orders.
Input: (10, [[0, 2, 4, 6]], [])
Expected Output: 60
Explanation: With no peak intervals, this matches the previous problem.
Hints
- Sweep over all times where something changes: a normal segment starts or ends, a wait segment starts or ends, or a peak interval starts or ends.
- For each constant segment, the pay is segment_length * effective_rate * (normal_active^2 + wait_active).