Greedy Algorithms & the Night Scheduler
Friday at Tunebox Live has one stage and a pile of DJs who want it. Each sent a set with a start and an end time, two sets can't share the stage, and the booker wants as many sets as possible. The fastest way there is to make one obvious-looking choice at a time and never look back. That's a greedy algorithm. Writing one is easy. The hard part is knowing when the obvious choice is actually safe.
The greedy idea: commit to the best-looking step
A greedy algorithm builds its answer one piece at a time. At every step it takes whatever looks best right now, commits, and never revisits that decision. No undo, no exploring alternatives. That's why greedy code is usually just a sort followed by one loop:
This only works when the problem has the greedy-choice property: some best answer begins with the greedy choice, so committing early never shuts you out of the optimum. The real work is picking which rule has that property.
Tempting rules that fail
"Best-looking" is carrying a lot of weight in that sentence. You could book the shortest set first, the earliest start first, or the earliest finish first. Try earliest start. It sounds fair, first come first served:
Shortest first fails too. Take [18–21], [20–22] and [21–24]. The short
middle set clashes with both neighbours, so booking it first leaves room for
nothing else. The two long sets would have fit together. Now sort the
marathon night by end time instead. Which set would be booked first?
night = [["Marathon", 18, 24], ["Opener", 18, 19], ["Warmup", 19, 20], ["Peak", 20, 22]]
by_end = sorted(night, key=lambda s: s[2])
print(by_end[0][0])Why earliest finish is safe
Take any best schedule and look at its first set. The set that finishes earliest overall (call it E) ends no later than that first set does. So swap them: put E where the first set was. Nothing after it can clash, because E frees the stage at least as early. You still have the same number of sets, and now the schedule starts with the greedy choice. Apply the same argument to the rest of the night, and greedy keeps pace with the optimum all the way to the end.
That's an exchange argument: show that any optimal answer can be rewritten to start with the greedy choice without getting worse. If you can write that paragraph, the greedy is proven. If you can't, what you have is a hunch.
❓ Cross-question: "Isn't this just a heuristic that happens to work?" Not here. A heuristic is usually good. Earliest finish is provably optimal for getting the most non-overlapping intervals. Change the goal, say to the biggest total crowd instead of the most sets, and the proof breaks. So does the greedy. You'll handle that version with dynamic programming in the capstone.
Step through the scheduler. Watch free_at move forward, and watch Kade get
turned away:
Back-to-back is not a clash
A set that ends at 20:00 and one that starts at 20:00 don't share a single minute of stage time. The comparison has to allow that:
All three back-to-back sets should be booked, so this should print 3. It prints 2.
Coming from Java/JS: the sort is the whole trick.
sets.sort((a, b) => a[2] - b[2])in JS, orArrays.sort(sets, Comparator.comparingInt(s -> s[2]))in Java. Python'skey=computes one key per item instead of comparing pairs. All three sorts are stable: items with equal keys keep their input order, and the task relies on that.
When greedy fails: the ident problem
Tunebox Radio fills short gaps with station idents. Say they come in 1, 3 and 4 seconds, and fewer idents sound better. The greedy rule is "take the longest one that still fits":
Now check every combination, fewest idents first:
from itertools import combinations_with_replacement
best = None
for count in range(1, 7):
for combo in combinations_with_replacement([1, 3, 4], count):
if sum(combo) == 6:
best = list(combo)
break
if best:
break
print(best)With lengths 1, 5, 10, 25 (the US coins), longest-first is optimal. With
1, 3, 4 it isn't. It's the same code on different numbers. The greedy-choice
property belongs to the problem, not to the code, and you'll solve fewest-idents
properly with a table in the Tabulation lesson.
Prove it, or distrust it
Before you trust a greedy rule:
- Try to break it by hand. One long item against several short ones is the classic counterexample.
- Write the exchange argument. If you can, you're done.
- Race it against brute force on small random inputs. Brute force is slow, but it can't be wrong.
❓ Cross-question: "When should I distrust a greedy?" When a choice uses up something later steps need, and whether that hurts depends on the exact numbers, as with idents filling a gap. Counting compatible things is often safely greedy. Exact totals and weights usually aren't.
| Operation | Time | Space |
|---|---|---|
| Sort sets by end time | O(n log n) | O(n) |
| One pass to book them | O(n) | O(n) for the result |
| Whole night scheduler | O(n log n) | O(n) |
| Brute force over every subset | O(2ⁿ · n) | O(n) |
Idioms & real-world patterns
operator.itemgetter for sort keys
itemgetter(2) is a ready-made lambda s: s[2]. It's slightly faster and reads
as "by column 2". Pass several indexes to sort on more than one key:
⚡ Advanced: fractional vs 0/1
If a playlist could take part of a track, greedy by rating-per-minute would be optimal: take the best ratio first, then a fraction of the next. That's the fractional knapsack. Make every track all-or-nothing and the same rule fails. That's the 0/1 knapsack, and it takes the table you'll build in the Tabulation lesson.
⚡ Advanced: "greedy stays ahead"
The exchange argument's twin: show that after every step, greedy's partial answer is at least as good as any other schedule's. After booking k sets, greedy's k-th set ends no later than the k-th set of any valid schedule. Ahead at every step means not behind at the end. Dijkstra's shortest-path algorithm is usually proven this way.
🎯 Your turn
Write schedule_sets(sets). Each set is [name, start, end]. Return the names of
the most sets that fit on one stage without overlapping, in the order they play.
schedule_sets([["Nova", 18, 20], ["Kade", 19, 21], ["Luma", 20, 22], ["Rex", 21, 23], ["Zed", 22, 24]])→["Nova", "Luma", "Zed"]schedule_sets([])→[]
A set may start exactly when the previous one ends. When two sets end at the same time, the one that comes first in the input is considered first.
Hint: sort by end time, keep the time the stage frees up, and book every set that starts at or after it.
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. ✅