Greedy Algorithms
When local choices lead to global optima: master the art of greedy algorithm design with proofs of correctness.
What are Greedy Algorithms?
A greedy algorithm builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. The key insight is that sometimes being "greedy" actually leads to the best overall solution.
Greedy Choice Property
A locally optimal choice leads to a globally optimal solution. At each step, the greedy choice is part of some optimal solution.
Optimal Substructure
An optimal solution contains optimal solutions to its subproblems. After making a greedy choice, the remaining problem is a smaller instance.
Warning: Not all problems have a greedy solution! Many problems that look like they could be solved greedily actually require dynamic programming. Always prove correctness.
Classic Greedy Algorithms
Activity Selection
O(n log n)Select the maximum number of non-overlapping activities
Greedy Strategy: Always pick the activity that finishes earliest
Fractional Knapsack
O(n log n)Maximize value while respecting weight limit (items can be fractioned)
Greedy Strategy: Sort by value/weight ratio, take greedily
Huffman Coding
O(n log n)Build optimal prefix-free binary codes for compression
Greedy Strategy: Always merge the two lowest frequency nodes
Dijkstra's Algorithm
O((V+E) log V)Find shortest paths in a weighted graph
Greedy Strategy: Always extend from the closest unvisited vertex
Prim's MST
O(E log V)Find minimum spanning tree of a graph
Greedy Strategy: Always add the cheapest edge connecting to the tree
Kruskal's MST
O(E log E)Find minimum spanning tree using edge sorting
Greedy Strategy: Sort edges by weight, add if no cycle formed
When to Use Greedy vs Dynamic Programming
Use Greedy When:
- • The greedy choice property holds
- • Making locally optimal choices leads to global optimum
- • The problem has optimal substructure
- • You can prove the greedy approach is correct
Use DP When:
- • Greedy fails (0/1 Knapsack, LCS)
- • You need to consider multiple choices
- • The problem has overlapping subproblems
- • Optimal solution requires global view
Explore More
Learn about advanced data structures that power efficient algorithms.