Capstone — Festival Planner
Tunebox Festival is one night with a main stage, a side stage and a hard curfew. Planning it means three decisions, and each one is a different shape of problem. The skill this capstone tests isn't any single algorithm. It's recognising which technique a problem is asking for, then wiring the pieces together so each one's output feeds the next.
Three questions, three shapes
Every act applies with [name, start, end, fans], in minutes after the doors
open. The house DJ's crate holds [title, minutes] tracks.
| Question | Shape | Technique |
|---|---|---|
| Which acts go on the main stage to draw the most fans? | non-overlapping intervals, maximise a weight | dynamic programming |
| Which leftover acts go on the side stage, as many as possible? | non-overlapping intervals, maximise the count | greedy, earliest finish |
| Which crate tracks fill the encore gap to curfew exactly? | list every exact combination | backtracking |
The first two rows look almost identical, and that's the trap.
Why greedy breaks once acts have weights
Earliest-finish greedy books the most acts. It says nothing about fans:
Three acts, 300 + 400 + 500 = 1200 fans. But Kade and Zed alone draw 1300. The exchange argument that proved earliest-finish swaps one act for another. That keeps the count the same, not the fans, so the proof says nothing about weights. Maximising weight means weighing every act against everything it excludes, and that's a DP.
Weighted interval scheduling
Sort the acts by end time. Let best[i] be the most fans from the first i
acts. Act i either sits out, giving best[i − 1], or it plays, giving
fans + best[p], where p is how many acts end by the time act i
starts. Those are exactly the acts that can play before it.
Because the end times are sorted, p is a binary search:
from bisect import bisect_right
ends = [60, 120, 150]
print(bisect_right(ends, 120))Now use the recurrence on one cell. The first two acts are done: best[1] = 300
(Nova) and best[2] = 800 (Kade). What about Luma?
best = [0, 300, 800, 0]
p = 1 # only Nova ends by 60, when Luma starts
best[3] = max(best[2], 400 + best[p]) # sit out, or play Luma's 400 after the best of the first p
print(best[3])Now step through the whole table for those three acts:
Reading the lineup back
As with the playlist packer, the table holds totals, so you walk back from the
end. Act i plays only if fans + best[p] beats best[i − 1]. If it
does, record the act and jump to p, since everything between p and i
overlaps it. If it doesn't, step to i − 1. On a tie the act sits out, so
the later-finishing act is the one dropped. It's the same tie rule as the
packer.
The main stage should be Kade and Zed. It prints four acts, and some of them overlap.
Composing the planner
Each stage of the pipeline consumes the one before it:
def plan_festival(acts, crate, curfew):
main, fans = main_stage(acts) # DP: most fans, no overlaps
leftovers = [a for a in acts if a not in main]
side = side_stage(leftovers) # greedy: most acts
encore = curfew - (main[-1][2] if main else 0)
mixes = exact_mixes(crate, encore) # backtracking: every exact fill
...Build each helper on its own, check it against the examples, and only then connect them. When the planner's output is wrong, you'll know which stage to blame.
❓ Cross-question: "Couldn't backtracking do all three?" It could, slowly. Trying every subset of acts is 2ⁿ. Forty applicants is about a trillion lineups, while the DP needs 40 table cells. Use backtracking where you need every answer, like the encore mixes. There the output itself can be exponential, so nothing faster exists.
❓ Cross-question: "Then why not DP for the encore?" DP can count the mixes in O(c · slot), like
count_fills. It can't list them any faster than backtracking, because listing costs at least as much as the list is long.
| Stage | Technique | Time |
|---|---|---|
| Main stage | sort + DP + binary search | O(n log n) |
| Side stage | sort + one greedy pass | O(n log n) |
| Encore | backtracking over c crate tracks | O(c · 2ᶜ) worst case |
| Whole planner | O(n log n + c · 2ᶜ) |
Idioms & real-world patterns
Recognising the shape
- "Most things that fit" and a swap argument works → greedy.
- "Best total", where choices interact through a budget or overlaps → DP. Define the state, write the recurrence, fill or memoize.
- "All of them", or a yes/no with heavy constraints → backtracking with pruning.
- Not sure? Write the brute force first. It becomes the test oracle for whatever you write next.
⚡ Advanced: the same DP, top-down
The recurrence doesn't care about direction. With @cache, the state is just i:
⚡ Advanced: when the problem grows
Add a second main stage and the state has to track two stages' free times, so the simple DP no longer applies. Add fees and a budget and the state gains a budget dimension, just like knapsack. That's this lesson's boss exercise. Most hard DP problems are an easy one with one more thing in the state.
🎯 Your turn
Write plan_festival(acts, crate, curfew). Acts are [name, start, end, fans] with
unique names. The crate is [title, minutes]. Return:
{
"main_stage": [...], # most total fans, no overlaps, in play order
"fans": ..., # their total fans
"side_stage": [...], # from acts NOT on the main stage: most acts, earliest finish
"encore": ..., # curfew minus the main stage's last end (the whole curfew if it's empty); never below 0
"encore_mixes": [...], # every crate combination filling the encore exactly; [] if encore is 0
}Rules. Back-to-back acts don't overlap. Sort by end time, keeping input order on ties. On the main stage, an act plays only if it strictly beats the best lineup without it (walk back from the last act). Encore mixes follow the mix-finder order: tracks in crate order, mixes by position.
- Acts Nova 0–60 (300), Kade 30–120 (800), Luma 60–150 (400), Rex 120–180 (350),
Zed 150–200 (500); crate Aurora 4, Blink 3, Cobalt 2, Drift 5, Echo 1; curfew 207
→ main
["Kade", "Zed"], fans1300, side["Nova", "Luma"], encore7, mixes[["Aurora", "Blink"], ["Aurora", "Cobalt", "Echo"], ["Cobalt", "Drift"]]
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green means this piece of the app is built. ✅