Introduction to Greedy Algorithms

This lesson defines the greedy paradigm, explains the greedy choice property and optimal substructure, contrasts greedy with dynamic programming and divide-and-conquer, shows when greedy succeeds or fails, and maps classic greedy problems to real-world applications.

What is a Greedy Algorithm?

A greedy algorithm builds a solution step by step. At each step it makes the choice that looks best right now (locally optimal), without reconsidering past decisions. If the problem has the right structure, those local choices combine into a globally optimal solution.

Greedy is not a single formula—it is a design paradigm. You sort or scan inputs, pick the best eligible option at each stage, and often prove that skipping alternatives cannot improve the final answer.

Schematic: Activity selection

Pick the activity that finishes earliest; repeat on what remains compatible:

Activities (start, finish):
  A: (1,4)  B: (3,5)  C: (0,6)  D: (5,7)  E: (8,9)

Sort by finish time → A(1,4), B(3,5), D(5,7), E(8,9), C(0,6)
Greedy pick: A → skip B (overlap) → D → E
Result: {A, D, E} — maximum non-overlapping set

Greedy Choice Property & Optimal Substructure

A problem is a strong greedy candidate when both properties hold:

1. Greedy Choice Property

A globally optimal solution can be reached by making a locally optimal (greedy) choice first, then solving the reduced subproblem.

Example: In activity selection, some activity with the earliest finish time belongs to an optimal schedule—you can safely take it first.

2. Optimal Substructure

After the greedy choice, the remaining subproblem must also admit an optimal solution (same as in DP).

Example: After picking activity A, the best schedule for remaining time slots is an optimal solution to the smaller set of compatible activities.

Note: Optimal substructure alone is not enough—many DP problems have it but need exploring multiple choices. Greedy additionally requires that one local choice is always safe.

Greedy vs DP vs Divide-and-Conquer

All three decompose problems, but commitments and storage differ:

Approach	Idea	Stores sub-answers?	Typical signal
Divide & Conquer	Split into independent parts, combine	Usually no table	Merge sort, closest pair of points
Greedy	One locally best irreversible choice per step	Often O(1) extra	Sort + pick; proof that greedy choice is safe
Dynamic Programming	Compare multiple choices; cache overlapping states	Table or memo map	0/1 knapsack, general coin change, LCS

Quick Comparison Examples

Greedy works — US coin change:

Amount: 30 cents, coins: [25, 10, 5, 1]
→ Take 25, then 5 → 2 coins ✓ (greedy optimal)

Greedy fails — arbitrary coin change:

Amount: 6, coins: [1, 3, 4]
Greedy: 4 + 1 + 1 = 3 coins
Optimal: 3 + 3 = 2 coins → need DP

Greedy works — fractional knapsack:

Items (weight, value): (10,60), (20,100), (30,120)
Value/weight: 6, 5, 4 → take highest ratio first, fractionally
Greedy gives maximum value for fractional items

When Greedy Works (and When It Fails)

Greedy is a good fit when

You can prove the greedy choice is always safe
Sorting by a key (ratio, deadline, finish time) drives decisions
Problem asks for max/min with matroid-like independence
Fractional versions allow taking parts of items

Switch to DP / other methods when

0/1 choices block future options (0/1 knapsack)
Coin systems are non-canonical
Multiple competing local optima must be compared
No exchange argument or matroid proof is available

Common Proof Techniques

Exchange argument: Show any optimal solution can be transformed to include the greedy choice without worsening the answer.
Staying ahead: Prove greedy is never worse than any other strategy at each step.
Matroid theory: Independence systems where greedy on sorted weights is optimal (e.g., minimum spanning tree).

Interview trap: A greedy-looking loop is not enough—state why the first greedy pick cannot exclude an optimal solution. If you cannot argue it, try DP.

Classic Greedy Problems

These map to the tutorials in this greedy track:

1. Scheduling & Intervals

Activity selection — max non-overlapping activities
Job sequencing with deadlines — max profit under deadlines

2. Resource & Encoding

Fractional knapsack — max value with divisible items
Huffman coding — minimum-length prefix codes

3. Coin & Change

Coin change (greedy) — when largest-coin-first is optimal

Real-Life Applications

Greedy methods appear wherever local best choices compose into good global plans:

Greedy family	Real-world use	Example
Activity / scheduling	Meeting rooms, CPU time slots, broadcast ads	Pack most non-overlapping meetings in a day
Fractional knapsack	Cargo loading, cloud budget splits	Fill truck by value-per-kg ratio
Huffman coding	File compression (ZIP, JPEG stages), streaming	Shorter codes for frequent symbols
Job sequencing	Manufacturing batches, ad campaign slots	Max profit jobs before deadlines
Coin change (greedy)	POS change, fare machines	US coins: quarters first
MST / routing	Network design, pipeline layout	Connect cities with minimum cable
Dijkstra	GPS navigation, game pathfinding	Shortest route on road networks

Cross-Domain Examples

Networking: Kruskal/Prim for minimum-cost backbone links
Finance: Greedy heuristics for portfolio rebalancing under constraints
Compression: Huffman trees in DEFLATE and media codecs
Operations: Job shop scheduling with deadline-driven ordering
Education: Canonical coin systems teach why greedy proofs matter

Learn the pattern, not just the puzzle: Recognizing “sort by finish time” or “sort by value/weight ratio” lets you reuse the same proof skeleton across interview problems.

Key Takeaway

Greedy = locally optimal choice + proof it is safe + often sort first.

Steps to Solve Greedy Problems

Identify the greedy criterion — What should be maximized/minimized at each step? (ratio, finish time, deadline)
Sort or prioritize — Order inputs so the best local choice is at the front.
Make irreversible choices — Pick the best feasible option; discard incompatible items.
Prove correctness — Exchange argument or greedy-choice lemma (interviews).
Implement & analyze — Usually O(n log n) from sorting; O(n) scan after sort.
Test counterexamples — Try small cases where greedy might fail; if it fails, use DP.

Next Steps

Continue Learning

Activity Selection — Classic interval scheduling with proof
Fractional Knapsack — Value/weight ratio greedy
Huffman Coding — Build optimal prefix codes
Dynamic Programming Intro — When greedy is not enough

Practice Problems

Beginner Level:

Intermediate Level:

Summary

Concept	Key Points
Definition	Build solution by repeated locally optimal choices
Properties	Greedy choice property + optimal substructure
Versus DP	Greedy commits; DP compares and stores alternatives
Typical complexity	O(n log n) sort + O(n) scan
Proof tools	Exchange argument, staying ahead, matroids
Goal	Simple, fast algorithms when greedy is provably optimal

Quick Reference Card

When to try greedy:

✓ Sorting by time, ratio, or deadline suggests itself
✓ Fractional or interval-style problems
✓ MST, Dijkstra, Huffman patterns
✓ You can articulate an exchange argument

When to avoid greedy:

✗ 0/1 knapsack (use DP)
✗ General coin change (use DP)
✗ Need to count ways or try many combinations

Compare with: Dynamic Programming for overlapping subproblems and multi-choice decisions.