Greedy Algorithms — Complete Step-by-Step Guide
Module 15 — Greedy Algorithms: Making the locally best choice at every step Structured as Topic → Plain-English Explanation → Real Code → Visual Diagram → Complexity → Common Pitfalls.
1. The Greedy Approach & The Greedy-Choice Property
A greedy algorithm constructs a solution piece by piece, always making the choice that offers the most immediate, local benefit at that exact moment — without ever looking backward or reconsidering past decisions.
Unlike Dynamic Programming, which exhaustively evaluates multiple overlapping decisions, a greedy algorithm makes one irreversible choice per step. It yields an optimal solution if and only if the problem exhibits two mathematical properties:
- Greedy-Choice Property: A globally optimal solution can always be reached by making locally optimal (greedy) choices.
- Optimal Substructure: An optimal solution to the overall problem contains optimal solutions to its subproblems.
2. Activity Selection / Interval Scheduling
Given $n$ activities with start time $s[i]$ and finish time $f[i]$, select the maximum number of mutually compatible (non-overlapping) activities that a single person or machine can perform.
The Greedy Rule: Sort by Finish Time
Always pick the activity that finishes earliest, because it leaves the maximum remaining time available for all subsequent activities.
struct Activity {
int start, finish, id;
};
bool compareFinish(const Activity& a, const Activity& b) {
return a.finish < b.finish;
}
vector<Activity> selectActivities(vector<Activity>& acts) {
sort(acts.begin(), acts.end(), compareFinish);
vector<Activity> selected;
int lastFinishTime = -1;
for (const auto& a : acts) {
if (a.start >= lastFinishTime) {
selected.push_back(a);
lastFinishTime = a.finish;
}
}
return selected;
}
3. Fractional Knapsack vs 0/1 Knapsack
- Fractional Knapsack: Items are continuous (like flour, gold dust, or oil). You can take any fraction $ rac{w}{W}$ of an item. Greedy works 100%: Sort items by their value-to-weight ratio ($val[i] / wt[i]$) in descending order and greedily take as much of the densest item as capacity allows. Time Complexity: $O(n log n)$ due to sorting.
- 0/1 Knapsack: Items are indivisible (take all or nothing). Greedy fails! Dynamic Programming ($O(n cdot W)$) is strictly required because taking the highest-density item might leave wasted space that prevents a better combination.
4. Classic Greedy Problems Matrix & Proof Methods
| Problem | Greedy Decision Rule | Time Complexity | Notes |
|---|---|---|---|
| Activity Selection | Earliest finish time first | $O(n log n)$ | Proved via Exchange Argument |
| Fractional Knapsack | Highest value/weight ratio first | $O(n log n)$ | Continuous optimization |
| Huffman Coding | Merge two lowest frequency trees | $O(n log n)$ | Optimal prefix-free code |
| Kruskal's MST | Add cheapest edge without creating cycles | $O(E log E)$ | Uses Disjoint Set (Union-Find) |
| Prim's MST | Connect nearest unvisited vertex | $O(E log V)$ | Uses Priority Queue |
| Dijkstra's Algorithm | Relax edges from closest known vertex | $O((V + E) log V)$ | Non-negative edge weights only |
