The idea: take the best bite now
A greedy algorithm behaves like a cashier making change: to hand back the fewest coins, you reach for the largest coin that still fits, again and again, without ever reconsidering an earlier pick. That is the whole shape of greedy — sort or prioritize the options, then repeatedly grab whatever looks best at the moment and commit to it. No backtracking, no exploring alternatives.
Because it never revisits a decision, greedy is usually fast and easy to code; the hard part is not the loop but knowing whether those quick local wins actually add up to the best overall answer. Watching a greedy run animate step by step makes the 'commit and never look back' behavior click almost immediately.
When greedy is provably correct
Greedy returns the true optimum only when the problem has two properties. First, the greedy-choice property: a globally optimal solution can always be reached by making a locally optimal choice. Second, optimal substructure: an optimal solution contains optimal solutions to its subproblems. If both hold, committing to the best-looking option at each step is safe.
Interval scheduling (activity selection) is the textbook success. To fit the most non-overlapping meetings into one room, sort by finish time and keep every meeting that starts after the last one you kept ends. A short exchange argument proves it: replacing any other first pick with the earliest-finishing one never leaves you worse off. The same provable local-choice safety underpins Huffman coding, Kruskal's and Prim's minimum spanning trees, and Dijkstra's shortest paths.
When greedy quietly gives the wrong answer
Greedy is seductive because it often looks right on the small inputs you test, then fails on ones you did not. Making change is the canonical trap. With US-style coins {1, 5, 10, 25}, grabbing the largest coin that fits is optimal — but change the set to {1, 3, 4} and ask for 6: greedy takes 4 + 1 + 1 (three coins), while 3 + 3 (two coins) is better. The local choice poisoned the global result.
When earlier choices constrain later ones like this, you need dynamic programming, which reconsiders combinations instead of committing to one. The rule of thumb: never trust greedy until you can back it with an exchange argument or find a counterexample. 'It passed my examples' is not a proof.
def max_meetings(intervals):
# Greedy: repeatedly pick the meeting that finishes earliest.
intervals.sort(key=lambda iv: iv[1]) # sort by finish time
count, last_end = 0, float("-inf")
for start, end in intervals:
if start >= last_end: # no overlap with last pick
count += 1
last_end = end # commit and never look back
return count
# max_meetings([(1, 3), (2, 5), (4, 7), (6, 9)]) -> 3Runtime is effectively the same best, worst, and average, because the sort runs regardless of input order. Heap-based greedy algorithms such as Dijkstra cost O((V + E) log V).
When to use it
- Interval or activity scheduling — fitting the most non-overlapping intervals by always keeping the earliest-finishing one.
- Any optimize problem where you can prove an exchange argument that a locally optimal choice is always safe.
- Classic graph and encoding problems that rely on provable local choices: Dijkstra, Kruskal/Prim MST, and Huffman coding.
- Coin change or resource allocation only when the denomination or cost structure is canonical (like standard currency).
Watch out for
- Assuming greedy is optimal without proof. Coins {1, 3, 4} making 6 give greedy 4+1+1 (three coins) when 3+3 (two coins) is better.
- Choosing the wrong priority or sort key — sorting intervals by start time or shortest duration instead of earliest finish gives suboptimal schedules.
- Reaching for greedy when subproblems overlap and choices interact; that situation needs dynamic programming, not a one-pass commit.
Greedy shows up constantly in interviews, usually disguised. Interviewers rarely say 'use greedy' — they hand you a maximize or minimize problem (schedule the most meetings, minimize total waiting time, jump to the end of an array, assign cookies to children) and watch whether you spot the greedy insight and, crucially, justify it. The signal they want is not just a working loop; it is you stating the greedy choice out loud ('always pick the earliest-finishing interval'), naming the sort or priority key, and defending why the choice is safe with a brief exchange argument. Strong candidates also acknowledge when greedy would break and what they would use instead (dynamic programming). Jumping straight to code with an unproven greedy rule is one of the most common ways a confident-looking solution gets rejected.