A greedy algorithm builds a solution step by step by always making the best choice available at the current moment. Once a choice is made, the algorithm usually does not go back and reconsider it. The hope is that a sequence of locally best decisions will lead to a globally optimal solution.
Greedy algorithms are attractive because they are often simple, fast, and easy to implement. However, they are not correct for every optimization problem. A greedy method works only when the structure of the problem supports greedy decisions.
The general pattern of a greedy algorithm is:
Examples of greedy rules include choosing the smallest edge, earliest finishing activity, highest profit-to-weight ratio, or nearest unvisited vertex.
A greedy algorithm is usually correct only if the problem has the following two properties:
If these properties do not hold, greedy may produce a fast answer, but not necessarily the best one.
A problem is a good candidate for a greedy approach if:
If a locally optimal choice can block a much better future solution, greedy is likely unsafe.
In exams and interviews, it is not enough to give a greedy rule. You must usually justify why it works. Common proof styles are:
| Feature | Greedy | Brute Force | Dynamic Programming |
|---|---|---|---|
| Strategy | Take best local choice | Try all possibilities | Solve overlapping subproblems |
| Backtracking | No | May or may not | No |
| Optimality | Only for suitable problems | Yes, if all cases checked | Yes, if recurrence is correct |
| Typical speed | Usually fast | Usually slow | Moderate to high |
| Examples | MST, Huffman, activity selection | Subset enumeration | 0/1 knapsack, LCS, matrix chain |
| Problem | Greedy Rule | Why It Works |
|---|---|---|
| Activity Selection | Choose activity with earliest finish time | Leaves maximum room for remaining activities |
| Fractional Knapsack | Choose highest value/weight ratio first | Fractions are allowed, so local ratio is safe |
| Huffman Coding | Merge two least frequent symbols | Builds optimal prefix-free code |
| Kruskal's MST | Take smallest edge that avoids a cycle | Safe by cut property |
| Prim's MST | Add smallest edge leaving current tree | Safe by cut property |
| Dijkstra's Algorithm | Finalize nearest unvisited vertex | Works when edge weights are non-negative |
Given a set of activities with start and finish times, choose the maximum number of non-overlapping activities. The correct greedy strategy is to always pick the activity that finishes earliest.
Why not choose the shortest activity or the earliest starting activity? Because those rules can block more activities later. Earliest finish time is the rule that leaves the most room for future selections.
import java.util.Arrays;
public class ActivitySelection {
static void selectActivities(int[] start, int[] finish) {
int n = start.length;
// Sort activities by finish time.
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> Integer.compare(finish[a], finish[b]));
System.out.println("Selected activities:");
int lastFinish = -1;
int count = 0;
for (int i : idx) {
if (start[i] >= lastFinish) {
System.out.println(" Activity " + i +
" [" + start[i] + ", " + finish[i] + "]");
lastFinish = finish[i];
count++;
}
}
System.out.println("Total: " + count + " activities");
}
public static void main(String[] args) {
int[] start = {1, 3, 0, 5, 8, 5};
int[] finish = {2, 4, 6, 7, 9, 9};
selectActivities(start, finish);
}
}import java.util.Arrays;
public class FractionalKnapsack {
static class Item {
int weight, value;
double ratio;
Item(int w, int v) {
weight = w;
value = v;
ratio = (double) v / w;
}
}
// Fractional knapsack works greedily because taking part of an item is allowed.
static double fractionalKnapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
Item[] items = new Item[n];
for (int i = 0; i < n; i++) items[i] = new Item(weights[i], values[i]);
Arrays.sort(items, (a, b) -> Double.compare(b.ratio, a.ratio));
double totalValue = 0;
int remaining = capacity;
for (Item item : items) {
if (remaining == 0) break;
if (item.weight <= remaining) {
totalValue += item.value;
remaining -= item.weight;
} else {
totalValue += item.ratio * remaining;
remaining = 0;
}
}
return totalValue;
}
public static void main(String[] args) {
int[] weights = {10, 20, 30};
int[] values = {60, 100, 120};
int capacity = 50;
System.out.printf("Maximum value: %.2f%n",
fractionalKnapsack(weights, values, capacity));
}
}Fractional knapsack allows taking part of an item, so choosing items by highest value-to-weight ratio is correct. This is a greedy problem.
0/1 knapsack allows either taking the whole item or leaving it. Here, the same greedy rule may fail. That problem is typically solved using dynamic programming.
This is one of the most important examples showing that a small change in problem constraints can completely change the correct algorithmic approach.
Huffman coding is a greedy method for building an optimal prefix-free binary code. The idea is simple: repeatedly combine the two least frequent symbols, because rare symbols can safely be placed deeper in the tree.
A priority queue is usually used so that the two minimum-frequency nodes can be selected efficiently at each step.
import java.util.PriorityQueue;
public class HuffmanCoding {
static class Node implements Comparable<Node> {
char ch;
int freq;
Node left, right;
Node(char ch, int freq) {
this.ch = ch;
this.freq = freq;
}
Node(int freq, Node left, Node right) {
this.freq = freq;
this.left = left;
this.right = right;
}
public int compareTo(Node other) {
return Integer.compare(this.freq, other.freq);
}
boolean isLeaf() {
return left == null && right == null;
}
}
static Node buildTree(char[] chars, int[] freqs) {
PriorityQueue<Node> pq = new PriorityQueue<>();
for (int i = 0; i < chars.length; i++) {
pq.add(new Node(chars[i], freqs[i]));
}
while (pq.size() > 1) {
Node left = pq.poll();
Node right = pq.poll();
pq.add(new Node(left.freq + right.freq, left, right));
}
return pq.poll();
}
static void printCodes(Node root, String code) {
if (root == null) return;
if (root.isLeaf()) {
System.out.printf(" '%c' (freq=%d): %s%n", root.ch, root.freq, code);
return;
}
printCodes(root.left, code + "0");
printCodes(root.right, code + "1");
}
public static void main(String[] args) {
char[] chars = {'a', 'b', 'c', 'd', 'e', 'f'};
int[] freqs = {5, 9, 12, 13, 16, 45};
Node root = buildTree(chars, freqs);
System.out.println("Huffman Codes:");
printCodes(root, "");
}
}Many graph algorithms use greedy ideas:
However, each of these works only under the right conditions. For example, Dijkstra's algorithm fails when negative edge weights are present.
Some problems appear greedy but are not. Common examples include:
Example: for coin values {1, 3, 4} and target 6, greedy gives 4 + 1 + 1 = 3 coins, but the optimal solution is 3 + 3 = 2 coins.
Many greedy algorithms follow this pattern:
Because of that, their running time is often O(n log n) or O(E log V) in graph problems.
| Feature | Greedy | Dynamic Programming |
|---|---|---|
| Decision style | Make the best local choice now | Compare many subproblem results |
| Revision of choices | No | Indirectly yes, through recurrence |
| Correctness | Only for suitable problems | Usually guaranteed if recurrence is correct |
| Speed | Often faster | Often uses more time and memory |
| Examples | Huffman, MST, activity selection | 0/1 knapsack, LCS, edit distance |
Explore 500+ free tutorials across 20+ languages and frameworks.