Algorithms
Greedy (Intro)
Difficulty: Intermediate
Given coin denominations of 1, 5, and 25, the greedy "take the largest coin that fits" strategy gives change optimally. Add a coin worth 10 to the system and greedy stays optimal. Replace 25 with 21 and greedy quietly breaks: making 63...
Greedy (Intro)
Given coin denominations of 1, 5, and 25, the greedy "take the largest coin that fits" strategy gives change optimally. Add a coin worth 10 to the system and greedy stays optimal. Replace 25 with 21 and greedy quietly breaks: making 63 cents now wants three 21s, but greedy says one 21 plus two 1s and ten more 1s. The same algorithm, the same input shape, and yet correctness depends entirely on a structural property of the problem.
Greedy (Intro) explains exactly which property that is. You will learn to test for the greedy-choice property and optimal substructure, the twin ingredients that justify a greedy decision. The lesson covers the canonical problems where greedy provably works (activity selection by earliest end time, fractional knapsack by value-to-weight ratio, job scheduling with deadlines, the jump game, Huffman encoding) and walks through the exchange-argument style of correctness proof. It also shows where greedy fails (0/1 knapsack, coin change with arbitrary denominations) so you know when to reach for DP instead.
In Sorting (Elementary), you saw why sorting often costs O(n log n); almost every greedy algorithm starts with a sort step. Big-O Notation (Upper Bound) gave you the language to express that cost.
Next, Dynamic Programming (Intro) picks up where greedy fails, when the local optimum does not guarantee the global one.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain the greedy strategy and identify the two properties (greedy choice property and optimal substructure) that guarantee correctness.
Solve the activity/interval selection problem by sorting and greedily choosing non-overlapping intervals.
Solve the fractional knapsack problem by sorting items by value-to-weight ratio.
Determine whether a greedy approach is valid for a given problem or if dynamic programming is needed.
Implement the jump game problem using a greedy furthest-reach approach.
Analyze the time complexity of greedy algorithms, typically dominated by the sorting step.
Why This Matters
01
Greedy algorithms often produce the simplest and most efficient solutions — when they work, they typically run in O(n log n) time due to an initial sort.
02
Activity selection and interval scheduling are among the most commonly tested medium-difficulty interview problems at top companies.
03
Understanding when greedy fails (e.g., 0/1 knapsack, coin change with arbitrary denominations) is essential for knowing when to switch to dynamic programming.
04
Many real-world optimization problems use greedy heuristics: Huffman encoding for compression, Dijkstra's algorithm for shortest paths, and Prim's/Kruskal's for minimum spanning trees.
Key Terms
6 terms you'll encounter in this lesson
Greedy choice property
A locally optimal choice at each step leads to a globally optimal solution. This is the key property that must hold for a greedy algorithm to be correct.
Optimal substructure
An optimal solution to the problem contains optimal solutions to its subproblems. Shared with dynamic programming, but greedy also requires the greedy choice property.
Activity selection
Given intervals with start and end times, select the maximum number of non-overlapping intervals. Solved greedily by sorting by end time and selecting the earliest-finishing compatible activity.
Fractional knapsack
Given items with weights and values and a weight capacity, maximize value by taking fractions of items. Solved greedily by sorting by value-to-weight ratio.
Exchange argument
A proof technique for greedy algorithms. Show that any optimal solution that differs from the greedy solution can be modified (exchanged) to match the greedy choice without worsening the result.
Greedy stays ahead
A proof technique showing that at every step, the greedy solution is at least as good as any other solution. Often used for interval scheduling.
Heads Up
Common misconceptions to watch out for
"Greedy always gives the optimal solution"
Greedy works only when the problem has the greedy choice property. For 0/1 knapsack or coin change with arbitrary denominations, greedy fails and dynamic programming is needed. Always verify the greedy choice property before using greedy.
"Sorting by start time gives the best interval schedule"
Sorting by start time can lead to selecting a long interval that overlaps with many shorter ones. Sorting by END time is correct because it leaves the most room for future intervals.
"Greedy and dynamic programming are completely different approaches"
Both require optimal substructure. The difference is that greedy makes one choice and never reconsiders, while DP considers all possibilities. Greedy is a special case of DP where the locally optimal choice is always globally optimal.