Greedy Algorithms from Scratch (2026)
Greedy algorithms make locally optimal choices at each step with the hope of finding a global optimum. They are simple, efficient, and work well for many optimization problems. The key is proving that the greedy choice property holds: making the locally optimal choice leads to a globally optimal solution. Greedy algorithms are often faster than dynamic programming and easier to implement.
In this tutorial, we will implement the activity selection problem, Huffman coding for data compression, and the fractional knapsack problem. We will learn to prove greedy correctness, identify when greedy works, and understand the limitations of the greedy approach.
Activity Selection Problem
The activity selection problem asks: given n activities with start and finish times, select the maximum number of non-overlapping activities. The greedy strategy is to always select the activity with the earliest finish time that is compatible with previously selected activities. This works because selecting the earliest finishing activity leaves the maximum room for future activities.
We sort activities by finish time, then iterate through them, selecting each activity that starts after the last selected activity ends. This greedy approach gives the optimal solution in O(n log n) time due to sorting.
def activity_selection(activities):
sorted_acts = sorted(activities, key=lambda x: x[1])
selected = [sorted_acts[0]]
last_finish = sorted_acts[0][1]
for i in range(1, len(sorted_acts)):
start, finish = sorted_acts[i]
if start >= last_finish:
selected.append((start, finish))
last_finish = finish
return selected
activities = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11)]
selected = activity_selection(activities)
print(f"Selected {len(selected)} activities:", selected)Huffman Coding
Huffman coding is a lossless data compression algorithm that assigns variable-length codes to characters based on their frequencies. More frequent characters get shorter codes, and less frequent characters get longer codes. The algorithm builds a Huffman tree by repeatedly combining the two lowest-frequency nodes until one tree remains.
The greedy choice is always combining the two smallest frequencies. This ensures that the most frequent characters are closest to the root (shorter codes). Huffman coding is optimal among prefix-free codes. It is used in ZIP files, JPEG compression, and HTTP/2 (HPACK).
#include
#include
#include
#include
using namespace std;
struct Node {
char ch; int freq;
Node *left, *right;
Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};
struct Compare { bool operator()(Node* a, Node* b) { return a->freq > b->freq; } };
void genCodes(Node* root, string code, unordered_map& hc) {
if (!root) return;
if (!root->left && !root->right) hc[root->ch] = code.empty() ? "0" : code;
genCodes(root->left, code+"0", hc);
genCodes(root->right, code+"1", hc);
}
Node* buildHuffman(string text) {
unordered_map freq;
for (char c : text) freq[c]++;
priority_queue, Compare> pq;
for (auto& p : freq) pq.push(new Node(p.first, p.second));
while (pq.size() > 1) {
Node *l = pq.top(); pq.pop();
Node *r = pq.top(); pq.pop();
Node* parent = new Node('\0', l->freq + r->freq);
parent->left = l; parent->right = r;
pq.push(parent);
}
return pq.top();
} Fractional Knapsack
The fractional knapsack problem allows taking fractions of items (not just whole items) to maximize value within a weight capacity. Unlike 0/1 knapsack, this problem has a greedy solution: sort items by value-to-weight ratio, then take as much as possible of each item in decreasing order of ratio.
The greedy approach works because we can take fractions - if an item doesn't fit completely, we take what we can and move to the next. This gives the optimal solution in O(n log n) time due to sorting.
import java.util.*;
public class FractionalKnapsack {
static double fractionalKnapsack(int capacity, int[][] items) {
Arrays.sort(items, (a, b) -> Double.compare((double)b[0]/b[1], (double)a[0]/a[1]));
double totalValue = 0;
int remaining = capacity;
for (int[] item : items) {
if (remaining >= item[1]) {
totalValue += item[0];
remaining -= item[1];
} else {
totalValue += item[0] * ((double) remaining / item[1]);
break;
}
}
return totalValue;
}
public static void main(String[] args) {
int[][] items = {{60,10},{100,20},{120,30}};
System.out.printf("Max value: %.2f%n", fractionalKnapsack(50, items));
}
}Greedy Correctness and Limitations
Not all optimization problems have greedy solutions. To prove a greedy algorithm works, we need to show: (1) Greedy choice property - the locally optimal choice leads to a global optimum, and (2) Optimal substructure - the optimal solution contains optimal solutions to subproblems. If either fails, greedy gives suboptimal results.
Classic example where greedy fails: the 0/1 knapsack problem (cannot take fractions). The greedy approach by value-to-weight ratio does not give the optimal solution. Dynamic programming is needed for 0/1 knapsack. Similarly, the coin change problem with arbitrary denominations may not have a greedy solution.
def greedy_coin_change(coins, amount):
result = []
for coin in sorted(coins, reverse=True):
while amount >= coin:
amount -= coin
result.append(coin)
return result if amount == 0 else None
def dp_coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i and dp[i - coin] + 1 < dp[i]:
dp[i] = dp[i - coin] + 1
return dp[amount] if dp[amount] != float('inf') else -1
us_coins = [25, 10, 5, 1]
print(greedy_coin_change(us_coins, 41)) # [25,10,5,1]
coins = [1, 3, 4]
print(greedy_coin_change(coins, 6)) # [4,1,1] = 3 coins (not optimal)
print(dp_coin_change(coins, 6)) # 2 coins: [3,3] (optimal)Frequently Asked Questions
When do greedy algorithms work?
Greedy works when the problem has greedy choice property (local optimum = global optimum) and optimal substructure. Examples: activity selection, Huffman coding, fractional knapsack, Dijkstra's algorithm.
What is the greedy choice property?
The greedy choice property states that making the locally optimal choice at each step leads to a globally optimal solution. It must be proven that no other choice could lead to a better solution.
Why does greedy fail for 0/1 knapsack?
In 0/1 knapsack, you cannot take fractions. The greedy approach by value-to-weight ratio may select items that don't fill the knapsack optimally. DP is needed because the problem lacks the greedy choice property.
How to prove greedy correctness?
Exchange argument: show that any non-greedy solution can be transformed into a greedy solution without losing value. Or use induction: show greedy makes correct choice at each step.
Originally published on Ayodhyyya. Last updated June 1, 2026.