Problem Statement
What is the key characteristic of a greedy algorithm?
Explanation
Greedy algorithms make the locally optimal choice at each step, hoping to find a global optimum. At each decision point, the algorithm chooses what appears best at that moment without considering future consequences.
Greedy algorithms do not always guarantee optimal solutions for all problems. They work when the problem exhibits greedy choice property, meaning a global optimum can be reached by making locally optimal choices, and optimal substructure, where an optimal solution contains optimal solutions to subproblems. Examples include Huffman coding, Dijkstra's algorithm, and activity selection.
Code Solution
SolutionRead Only
// Activity Selection - Greedy approach
int activitySelection(int[] start, int[] finish) {
// Sort by finish time
sort(start, finish);
int count = 1; // First activity
int lastFinish = finish[0];
// Greedy: Pick activity with earliest finish time
for (int i = 1; i < start.length; i++) {
if (start[i] >= lastFinish) {
count++;
lastFinish = finish[i];
}
}
return count;
}
// Greedy choice: Always pick earliest finishing activity
// Time: O(n log n)
// Coin Change - Greedy may fail
// Coins: [1, 3, 4], Amount: 6
// Greedy: 4 + 1 + 1 = 3 coins
// Optimal: 3 + 3 = 2 coins
// Greedy doesn't work for all coin systems!Practice Sets
This question appears in the following practice sets:
