Maximize Delivery Pay - Dynamic Programming to Maximize Dasher Earnings

Question

## Round 1 - Coding

## Problem

A dasher has a fixed shift window. They are given a list of available delivery jobs, each with a start time, end time, and payout. A dasher can only do one job at a time and cannot start a new job until the previous one finishes. Find the maximum total payout achievable within the shift.

```python
def maximize_delivery_pay(
    jobs: list[tuple[int, int, float]]  # (start, end, pay)
) -> float:
    # jobs are sorted by end time
    # Returns maximum achievable payout (non-overlapping jobs)
    ...
```

```
Example:
jobs = [
    (1,  3, 10.0),
    (2,  5, 15.0),
    (4,  7, 12.0),
    (6,  9, 18.0),
    (1, 10, 25.0),
]
# Optimal: job(1,3,10) + job(4,7,12) + job(8,9,?) or
#          job(2,5,15) + job(6,9,18) = 33.0
maximize_delivery_pay(jobs) -> 33.0
```

## Approach

Sort by end time. For each job `j`, `dp[j] = max(dp[j-1], pay[j] + dp[last non-overlapping job])`. Use binary search to find the last compatible job.

## Follow-ups

1. What is the time complexity of your DP solution?
2. How does binary search help find the last non-overlapping job efficiently?
3. How would you reconstruct which jobs to take (not just the maximum value)?
4. How does this problem change if a dasher can carry two simultaneous deliveries?

Maximize Delivery Pay - Dynamic Programming to Maximize Dasher Earnings

Question Details

Full Details

Topics

More from DoorDash