The coding question
A Dasher has a list of deliveries for the day, each with a start time, end time and pay. They can only do one at a time. What's the most they can earn?
Ask a few questions first
| Ask | What we'll assume |
|---|---|
| Can a delivery start the moment another one ends? | Yes. End at 3, start at 3 is fine. |
| Are times whole numbers? | We'll assume numbers that can be compared, like minutes since midnight. |
| Can the list be empty? | Yes. The answer is 0. |
| Do you need the deliveries, or just the total? | Just the total. Picking the deliveries comes up in the follow-ups. |
A couple of examples
| Input | Output |
|---|---|
| [(1, 3, 5), (2, 5, 6), (4, 6, 5), (6, 7, 4), (5, 8, 11), (7, 9, 2)] | 17 ((2, 5, 6) then (5, 8, 11)) |
| [(1, 4, 10), (2, 3, 4), (3, 5, 4)] | 10 (the one long delivery beats the two short ones) |
| [(1, 2, 5), (2, 3, 5), (3, 4, 5)] | 15 (back to back is allowed) |
| [] | 0 |
Start with brute force
Try every subset of deliveries. For each one, sort by start time and check that no two overlap. Keep the biggest total pay.
Cost: There are 2ⁿ subsets, so O(2ⁿ × n). That's fine for 15 deliveries and hopeless for 50.
A better way
Greedy picks don't work. Taking the highest pay first, or the one that ends earliest, can both be wrong. In the second example, ending earliest picks the two short deliveries for 8, but the long one pays 10.
So use dynamic programming. Sort deliveries by end time. For each delivery, there are only two choices: skip it, and keep the best you had without it, or take it, and add its pay to the best you could do with deliveries that end by the time it starts.
Because the end times are sorted, 'deliveries that end by the time this one starts' is always a prefix of the list. Find where that prefix stops with a binary search on the end times instead of scanning back.
- Sort the deliveries by end time and pull out a list of end times.
- Make best, where best[i] is the most pay using only the first i deliveries. best[0] is 0.
- For delivery i, binary search the end times for how many finish at or before its start. Call that fits.
- best[i + 1] is the bigger of best[i] (skip it) and best[fits] + its pay (take it).
- Return the last value in best.
The code
from bisect import bisect_right
def most_pay(deliveries):
# deliveries: list of (start, end, pay). One can start when another ends.
deliveries = sorted(deliveries, key=lambda d: d[1])
ends = [end for _, end, _ in deliveries]
# best[i] = most pay using only the first i deliveries, by end time.
best = [0] * (len(deliveries) + 1)
for i, (start, end, pay) in enumerate(deliveries):
# How many deliveries finish by the time this one starts.
fits = bisect_right(ends, start, 0, i)
best[i + 1] = max(best[i], best[fits] + pay)
return best[-1]| Cost | Why | |
|---|---|---|
| Time | O(n log n) | Sorting, then one binary search per delivery |
| Space | O(n) | The sorted copy, the end times and the best list |
Test it
Walk through one of the examples out loud, then check the cases that tend to break things:
- No deliveries. Return 0.
- One delivery ending exactly when the next starts, like the third example. bisect_right counts it as fitting.
- Two deliveries with the exact same times. Only one can be picked, so you get the higher pay.
- Every delivery overlaps every other one. The answer is the single best pay.
- Deliveries given in a random order. Sorting by end time handles it.
Common mistakes
- Going greedy by pay or by earliest end. Both fail on simple inputs, so show a counter-example before you move on.
- Using bisect_left instead of bisect_right. Then a delivery that ends exactly when this one starts doesn't count as fitting.
- Sorting by start time but searching end times. The search only works on the list you sorted by.
- Searching the whole end times list instead of just the deliveries before this one. With zero-length deliveries that can count the current one.
Follow-up questions
How would you return which deliveries to take?
Walk back from the end. At each i, if best[i + 1] is bigger than best[i], delivery i was taken, so add it and jump to fits - 1. Otherwise move to i - 1.
What if the Dasher can carry two deliveries at once?
That's a harder problem. One way is to track the end times of both slots in the state, which grows fast. For small inputs you can run the same idea with two 'free at' times instead of one.
What if there's travel time between deliveries?
Treat each delivery as ending a bit later, by the time it takes to get to the next pickup. If travel depends on where the next one is, the simple prefix trick breaks and you need a graph of which delivery can follow which.
How the time adds up
| Minutes | What you're doing |
|---|---|
| 0–5 | Ask about touching times and empty input |
| 5–10 | Brute force: try every subset, and show why greedy fails |
| 10–20 | Sort by end time, take or skip each one |
| 20–35 | Write the code |
| 35–40 | Test it on the examples and edge cases |
| 40–45 | Follow-up questions |
Key concepts used here
- Dynamic programmingSolve each subproblem once and reuse the answer.
- Binary searchCut the search in half, even when you're searching for an answer.
- IntervalsMerge, insert and schedule ranges without tripping over the edges.
We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by DoorDash.