principlejavascriptModerate
Greedy algorithms: make the locally optimal choice when global optimum follows
Viewed 0 times
greedy algorithminterval schedulinggreedy choice propertyexchange argumentactivity selection
Problem
Greedy algorithms look similar to DP but are not always correct. Developers apply greedy to problems that require DP (like 0-1 knapsack), or fail to apply greedy to problems where it is provably optimal (like activity selection).
Solution
Greedy works when the problem has the greedy choice property: a global optimum can be reached by always choosing the locally optimal option. Verify with an exchange argument: assume any optimal solution, show you can swap in the greedy choice without making it worse.
Why
Interval scheduling (sort by end time, always pick earliest-ending non-overlapping interval) has the greedy choice property. Fractional knapsack does too. 0-1 knapsack does not — you need DP.
Gotchas
- Coin change with arbitrary denominations is NOT greedy-solvable — DP is required (greedy fails for coins [1,3,4] with target 6)
- Huffman coding is a greedy algorithm with a formal proof of optimality
- When greedy fails, the counterexample is usually a small 3-5 element case — test these before trusting greedy
Code Snippets
Greedy activity selection by earliest end time
// Activity selection: maximum non-overlapping intervals
// Greedy: sort by end time, pick earliest-ending non-overlapping
function activitySelection(intervals) {
intervals.sort((a, b) => a[1] - b[1]); // sort by end time
const selected = [];
let lastEnd = -Infinity;
for (const [start, end] of intervals) {
if (start >= lastEnd) {
selected.push([start, end]);
lastEnd = end;
}
}
return selected;
}Context
Interval scheduling, task selection, resource allocation, or any optimization where local choice is globally safe
Revisions (0)
No revisions yet.