Greedy: Activity Selection
Medium+90 XPPick the most non-overlapping activities by sorting on END time and always grabbing the next one that fits.
No visualization loaded.
Watch
—
Press Run to begin.
You have a bunch of activities, each with a start and end time, and you can only do one at a time. You want to do as MANY as possible without two overlapping. A greedy method solves it: sort the activities by when they finish, then sweep through and grab each one that starts after your last pick ended.
▸What does 'greedy' even mean?
Greedy means: at each step, grab the choice that looks best RIGHT NOW and never undo it. No planning ahead, no backtracking, no comparing every possibility — just commit to the locally-best move and keep going. It's the opposite of carefully trying all combinations. The surprising part is that for some problems this simple, stubborn strategy actually gives the perfect answer.
▸Why sort by END time? That feels random.
Because the activity that FINISHES earliest leaves the most room for everything after it. Think of your day as a hallway: picking the activity that gets out of the way soonest keeps the most open space for later activities to fit. So 'earliest finish' isn't random — it's the choice that protects the most future room, which is exactly what lets you fit the maximum number.
▸Why not just take the SHORTEST activity first? That seems greedier.
It can wreck the answer. Picture three activities: A = 1-5, B = 4-6, C = 5-9. The shortest is B (only 2 long), so 'shortest first' grabs B — but B overlaps BOTH A and C, so you end up with just 1 activity. Sorting by end time instead takes A (ends at 5) then C (starts at 5): 2 activities. 'Shortest first' looked clever and lost.
▸What about taking the EARLIEST start first?
Also broken. Imagine A = 0-10 and then B = 1-2, C = 3-4, D = 5-6. 'Earliest start' grabs A first — but A hogs the whole day and blocks B, C, and D, giving you 1 activity. 'Earliest end' skips the greedy-looking giant A and collects B, C, D instead: 3 activities. The earliest-FINISH rule is the only one of the three that's provably correct here.
▸When does greedy work, and when do I need something heavier like DP?
Greedy works when a problem has the 'safe first move' property: there's always a locally-best choice you can lock in without it ever blocking the best overall answer — like 'earliest end' here. When that's NOT true — when a choice that looks best now can force worse choices later (think 0/1 Knapsack, where grabbing the most valuable item can waste the bag) — greedy gives wrong answers and you need Dynamic Programming, which actually weighs the alternatives instead of committing blindly.
How the work grows
O(n log n) is good — the practical sorting speed. The work is dominated by sorting the activities by end time: O(n log n). The greedy sweep afterward is a single left-to-right pass that touches each activity once — O(n) — so the sort is the expensive part. No table, no recursion: greedy's payoff is that one pass replaces the exponential 'try every subset' search.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.