Theory
A greedy algorithm builds a solution step by step by choosing what appears to be the best option at the current moment. Greedy strategies can produce optimal solutions for certain problems, but they do not work for every optimization problem.
Example
const coins = [10, 5, 2, 1];
let amount = 28;
let count = 0;
for (const coin of coins) {
while (amount >= coin) {
amount -= coin;
count++;
}
}
console.log(count);
Expected Output
The algorithm uses the available denominations greedily.
Practice
Solve a simple activity-selection problem using a greedy approach.
Interview Questions
- What is a greedy algorithm?
- Does greedy always produce an optimal solution?
- What is a locally optimal choice?
- Give examples of greedy algorithms.