Greedy Algorithms
Algorithms·intermediate·~35 min read
- greedy
- algorithm
- pattern
What you'll learn
The Golden Rule
"Make the locally optimal choice at each step, and it leads to the globally optimal solution." This single sentence captures the essence of greedy algorithms. Unlike dynamic programming which explores all possibilities, a greedy algorith…
Greedy vs Dynamic Programming
| Aspect | Greedy | Dynamic Programming | |--------|--------|-------------------| | Choices | Makes ONE choice, moves forward | Considers ALL choices | | Subproblems | Solves one subproblem after choosing | Solves many subproblems before…
When Greedy Fails: Counterexamples
How to Validate If Greedy Works (Counter-Example Method)
The most straightforward way to determine if greedy applies: 1. Propose a greedy strategy 2. Try to construct an input where the greedy choice leads to a suboptimal result 3. If no counter-example exists → greedy likely works 4. If you f…
Classic Counter-Examples
Coin Change -- Consider making change for 30 cents with coins [25, 15, 1]: - Greedy (pick largest first): 25 + 1 + 1 + 1 + 1 + 1 = 6 coins - Optimal: 15 + 15 = 2 coins The greedy choice (take the biggest coin) locks us into a suboptimal…
Pattern 1: Interval Scheduling / Activity Selection
Core Idea
Given intervals, select the maximum number of non-overlapping intervals. Sort by end time, then greedily pick the interval that finishes earliest (leaving maximum room for future intervals).
Why Sort by End Time?
Sorting by start time fails: Sorting by end time ensures each pick "uses up" the least future time:
Implementation Pattern
Variations
Minimum number of intervals to remove for non-overlapping: total - maxnonoverlapping. Minimum meeting rooms (overlapping intervals): This is NOT a simple greedy pick -- use a min-heap tracking end times of active meetings, or count overl…
Pattern 2: Huffman-Style Frequency Processing
Core Idea
When combining items has a cost proportional to their sizes, always combine the two smallest items first. This minimizes total cost because smaller items get "combined" more times (deeper in the tree).
Connect Ropes (Minimum Cost)
Given rope lengths [4, 3, 2, 6], find minimum cost to connect all into one rope (cost = sum of two ropes being connected): Why greedy works: Ropes connected earlier contribute their length to every future connection. Connecting small rop…
Reorganize String
Place characters so no two adjacent are the same. Greedy: always place the most frequent remaining character (that differs from the last placed). Use a max-heap of (frequency, character): ---
Pattern 3: Jump Game / Reach
Core Idea
Track the farthest position reachable from positions seen so far. At each step, update the maximum reach.
Can You Reach the End?
Minimum Jumps to End
Greedy: track the end of the current jump range. When you reach it, you must take another jump. The farthest you can reach within the current range becomes the next range end. ---
Pattern 4: Gas Station / Circular Route
Core Idea
For a circular route with gas stations, determine if a complete circuit is possible and find the starting station. Key insight: If total gas >= total cost, a solution exists. The starting point is where the cumulative deficit resets (the…
Pattern 5: Task Scheduling with Cooldown
Core Idea
Given tasks with a cooldown period between identical tasks, find the minimum time to complete all tasks. Greedy: schedule the most frequent task first, then fill cooldown slots with other tasks.
Slot-Based Analysis
But if there are enough different tasks, the formula might give less than total tasks. The answer is: ---
Pattern 6: Fractional Knapsack
Core Idea
Unlike 0/1 knapsack (which requires DP), fractional knapsack allows taking fractions of items. Greedy by value-to-weight ratio works perfectly. Why greedy works for fractional but not 0/1: With fractions, you can always take the "best re…
Pattern 7: Partition Labels
Core Idea
Partition a string into maximum parts such that each character appears in at most one part. Greedy: track the last occurrence of each character, then extend the current partition boundary to include all characters' last occurrences. Why…
Proving Greedy Correctness: The Exchange Argument
The informal exchange argument has three steps: 1. Assume an optimal solution exists that differs from the greedy solution. 2. Show you can "exchange" a choice in the optimal solution for the greedy choice without worsening the result. 3…
Common Mistakes
1. Applying greedy to 0/1 problems: Knapsack, coin change with arbitrary denominations, longest increasing subsequence -- these need DP. 2. Wrong sorting criterion: Sorting by start time instead of end time for activity selection, or sor…
Complexity Analysis
| Pattern | Time Complexity | Space Complexity | Bottleneck | |---------|----------------|-----------------|------------| | Interval scheduling | O(n log n) | O(1) | Sorting | | Huffman / Connect ropes | O(n log n) | O(n) | Heap operatio…
Summary: When to Reach for Greedy
Ask yourself: 1. Can I sort the input by some criterion and make a one-pass decision? 2. Does the locally best choice at each step lead to the globally best answer? 3. If I commit to this choice now, can I still solve the remaining probl…
Template Properties
- Sorting is almost always the first step -- it enables the greedy ordering. Whether by end time (intervals), by ratio (knapsack), or by frequency (Huffman), the sort defines which choice is "locally best." - The "No Backtracking" proper…