How to solve optimisation problems by always making the locally best choice at each step, trusting that local optima combine into a global optimum. When greedy works it is elegant and fast — when it does not, it produces wrong answers without error messages, which is exactly what happened with a medical scheduling system that caused a legal complaint.
Know the classic correct greedy problems: interval scheduling, activity selection, minimum spanning tree (Kruskal, Prim). Be able to explain WHY the greedy criterion is correct for each, not just what it is.
Design systems that use greedy algorithms at scale: network routing (OSPF uses Dijkstra), file compression (Huffman), scheduling. Know how to validate greedy correctness with exchange arguments and counterexamples.
How to solve optimisation problems by always making the locally best choice at each step, trusting that local optima combine into a global optimum. When greedy works it is elegant and fast — when it does not, it produces wrong answers without error messages, which is exactly what happened with a medical scheduling system that caused a legal complaint.
Developer chooses earliest-start greedy strategy for appointment scheduling — seems intuitive
System approves overlapping appointments for the same doctor — no error thrown, scheduling appears to succeed
WARNINGDoctor and patient arrive for same appointment slot — double-booking confirmed
CRITICALFormal legal complaint filed against clinic for scheduling failure
CRITICALScheduling rewritten with earliest-finish greedy — provably maximises non-overlapping appointments
The question this raises
Greedy algorithms can produce plausible-looking but wrong answers. How do you know whether a greedy approach is provably correct or just usually correct?
You need to pack as many non-overlapping meetings as possible into one conference room. You have meetings at various times and durations. Which greedy criterion provably gives the maximum number of non-overlapping meetings?
Lesson outline
The meeting room problem
You need to pack as many meetings as possible into a single conference room. You have 6 meeting requests. Greedy with earliest start picks the 8am-5pm all-day meeting first — nothing else fits. Greedy with earliest finish picks the 8am-9am standup first, then the 9:30am-10am call, then the 10:15am-11am workshop — three meetings fit. The criterion you choose (earliest start vs earliest finish) determines whether you get the right answer. Earliest finish is provably optimal for this problem.
Greedy Algorithm
Sort by the greedy criterion For each item in sorted order: if it fits, take it
Use for: Reach for greedy when the problem asks for maximum or minimum of something and you can identify a single criterion that is provably correct. Always justify the criterion before coding — if you cannot justify it, use DP instead.
The key insight: greedy works when making the locally best choice now cannot make the overall solution worse. The proof is always an exchange argument: take any optimal solution that does not start with the greedy choice, swap the first choice to the greedy one, and show the solution is at least as good. If you can always make this swap, greedy is provably correct.
How this concept changes your thinking
I need to schedule the most meetings in one room
“I pick meetings by earliest start time — longest meeting comes first and blocks the whole day”
“I sort by earliest finish time. A meeting that finishes earliest leaves the most room for future meetings. This is the provably correct criterion.”
I need minimum coins to make £47 using 1p, 2p, 5p, 10p, 20p, 50p coins
“I try every combination of coins until I find the minimum — exponential search”
“Greedy works here because standard denominations have the "greedy property": taking the largest coin that fits never prevents an optimal solution. Always take the largest coin that does not exceed the remaining amount.”
I need minimum coins using coins [1, 3, 4] to make 6
“Greedy: take 4 (largest ≤6), then take 1+1 = 3 coins total”
“Wrong! 3+3 = 2 coins is better. Greedy fails for non-standard denominations — use DP instead.”
Interval scheduling: fit maximum meetings in one room
01
Input. Six meetings: [9am-5pm all-day], [8am-9am standup], [9:30am-10am check-in], [10:15am-11am workshop], [11:30am-1pm lunch], [2pm-5pm planning]. Goal: fit as many as possible in one room.
02
Sort by finish time. Sorted order: standup (ends 9am), check-in (ends 10am), workshop (ends 11am), lunch (ends 1pm), planning (ends 5pm), all-day (ends 5pm).
03
Pick standup. It ends at 9am. No conflict. Room is booked until 9am.
04
Pick check-in. Starts at 9:30am — after our current end of 9am. No conflict. Room booked until 10am.
05
Pick workshop. Starts at 10:15am — after 10am. No conflict. Room booked until 11am.
06
Pick lunch. Starts at 11:30am — after 11am. No conflict. Room booked until 1pm.
07
Skip planning. Starts at 2pm — after 1pm, no conflict. Pick it. Room booked until 5pm. Result: 5 meetings fit. The all-day meeting was never selected — its early start made it look attractive but its late finish blocked everything.
Input. Six meetings: [9am-5pm all-day], [8am-9am standup], [9:30am-10am check-in], [10:15am-11am workshop], [11:30am-1pm lunch], [2pm-5pm planning]. Goal: fit as many as possible in one room.
Sort by finish time. Sorted order: standup (ends 9am), check-in (ends 10am), workshop (ends 11am), lunch (ends 1pm), planning (ends 5pm), all-day (ends 5pm).
Pick standup. It ends at 9am. No conflict. Room is booked until 9am.
Pick check-in. Starts at 9:30am — after our current end of 9am. No conflict. Room booked until 10am.
Pick workshop. Starts at 10:15am — after 10am. No conflict. Room booked until 11am.
Pick lunch. Starts at 11:30am — after 11am. No conflict. Room booked until 1pm.
Skip planning. Starts at 2pm — after 1pm, no conflict. Pick it. Room booked until 5pm. Result: 5 meetings fit. The all-day meeting was never selected — its early start made it look attractive but its late finish blocked everything.
Interval scheduling with earliest-finish greedy — provably optimal for maximising non-overlapping intervals. The sort is the entire insight.
1def interval_scheduling(intervals: list) -> list:2# intervals: list of (start, end) tuples3if not intervals:4return []5# Sort by finish time — this is the greedy criterion7intervals.sort(key=lambda x: x[1])Sort by finish time (x[1]), not start time (x[0]). Sorting by start time gives earliest-start greedy which is NOT optimal for this problem. This one choice determines correctness.8selected = [intervals[0]] # always take the first (earliest finish)Always take the first interval after sorting — the one with the earliest finish time is always part of an optimal solution (exchange argument: you can swap any other first choice for this one and not do worse).10last_end = intervals[0][1]11for start, end in intervals[1:]:The only check: does this interval start at or after the last selected interval ends? If yes, it is compatible and greedy says take it.13if start >= last_end: # no overlap with last selected14selected.append((start, end))Update last_end to end, not to last_end. You want the finish time of the most recently selected interval, not a running maximum.15last_end = end # update the boundary16return selected
The intuitive greedy criterion for meeting scheduling is earliest start, not earliest finish. Earliest start feels natural (process things in order) but is not optimal. It is a silent wrong answer — produces a valid (non-overlapping) schedule but not the maximum one.
Wrong greedy criterion: earliest start instead of earliest finish
# WRONG greedy criterion — earliest start
def interval_scheduling_wrong(intervals):
intervals.sort(key=lambda x: x[0]) # sort by START
selected = [intervals[0]]
last_end = intervals[0][1]
for start, end in intervals[1:]:
if start >= last_end:
selected.append((start, end))
last_end = end
return selected
# On [(7,17), (8,9), (9,10), (10,11)]:
# Picks (7,17) first. Nothing else fits. Returns 1 meeting.
# Correct answer: 3 meetings [(8,9),(9,10),(10,11)]# CORRECT: sort by finish time
def interval_scheduling(intervals):
intervals.sort(key=lambda x: x[1]) # sort by FINISH
selected = [intervals[0]]
last_end = intervals[0][1]
for start, end in intervals[1:]:
if start >= last_end:
selected.append((start, end))
last_end = end
return selected
# On [(7,17),(8,9),(9,10),(10,11)]:
# Picks (8,9), then (9,10), then (10,11). Returns 3 meetings.Both versions produce non-overlapping schedules. Only the right version produces the maximum non-overlapping schedule. The earliest-start version silently returns fewer meetings with no error — in production you might never notice unless you verify the count. The lesson: before using greedy, state and justify the criterion. "Earliest finish because a short meeting leaves more room for future meetings" is a justification. "Earliest start because we process things in order" is not.
| Scenario | What happens | Speed |
|---|---|---|
| Interval scheduling (n meetings) | Sort by finish time, one pass to select | Fast (O(n log n)) |
| Coin change with standard denominations (1p, 2p, 5p...) | Take largest coin that fits, repeat | Fast (O(amount / min_coin)) |
| Coin change with arbitrary denominations | Greedy gives wrong answer — must use DP | Use DP (O(amount × coins)) |
| Dijkstra shortest path (greedy by edge weight) | Always expand cheapest unvisited node | Fast (O((V+E) log V)) |
Greedy Algorithms
📖 What the exam expects
A greedy algorithm makes the locally optimal choice at each step. It is correct when the problem has the "greedy choice property" (local optima compose into a global optimum). Classic correct greedy: interval scheduling (sort by finish time), Huffman encoding, Dijkstra. Classic greedy failures: 0-1 knapsack, coin change with non-standard coins.
Toggle between what certifications teach and what production actually requires
Greedy problems in interviews are often disguised as scheduling, resource allocation, or coverage problems. Giveaway phrases: "maximum non-overlapping intervals", "minimum platforms needed", "assign tasks to minimise total time", "minimum spanning tree". The challenge is identifying the correct criterion — interviewers will probe this directly.
Common questions:
Strong answer: states the greedy criterion and immediately justifies it / tests the criterion with a small adversarial example before coding / knows the classic correct greedy problems by name / knows when to switch from greedy to DP
Red flags: uses greedy without justifying the criterion / picks earliest start for interval scheduling / cannot produce a counterexample to test the greedy criterion / does not mention when greedy fails and DP is needed
💡 Analogy
You have a suitcase with a weight limit and you want to pack as much value as possible. Greedy says: take the most valuable item that fits, then the next most valuable, and so on. This works perfectly for the fractional knapsack (you can take half a diamond). It fails for the 0-1 knapsack (you cannot take half a diamond). The difference: in the fractional case, a locally optimal choice (highest value per kg) is always globally optimal. In the 0-1 case, a large valuable item might block several smaller items whose combined value is higher.
⚡ Core Idea
A greedy algorithm never looks back. It picks the best available option right now and moves on. This is only provably correct when the problem has the "greedy choice property": making the locally optimal choice at each step is always compatible with a globally optimal solution. Proving this is the hard part. Most greedy algorithms require a proof (often an exchange argument: assume the greedy solution is not optimal, show you can swap choices to make it greedy without making it worse).
🎯 Why It Matters
When greedy is provably correct, it is the best algorithm you can have: O(n log n) for problems that would require O(n!) exhaustive search. Dijkstra's shortest-path algorithm is greedy. Huffman encoding (used in every JPEG and MP3 file) is greedy. The interval scheduling that packs the most meetings into a calendar is greedy. Understanding when greedy works and when it does not separates engineers who ship correct solutions from engineers who ship plausible-looking wrong answers.
Ready to see how this works in the cloud?
Switch to Career Paths for structured paths (e.g. Developer, DevOps) and provider-specific lessons.
View role-based pathsSign in to track your progress and mark lessons complete.
Questions? Discuss in the community or start a thread below.
Join DiscordSign in to start or join a thread.