Definition: What Is Greedy Algorithm?
A Greedy Algorithm makes the locally optimal choice at each step, hoping it leads to a globally optimal solution. Greedy algorithms choose the best option available at the current moment without considering future consequences. They are simple and efficient, but don't always give the optimal solution.
Greedy algorithms work when local optimal choices lead to global optimum. This requires two properties: greedy choice property (locally optimal choice is part of globally optimal solution) and optimal substructure (optimal solution contains optimal solutions to subproblems).
Greedy algorithms are fast (typically O(n log n) or O(n)) and simple to implement. They're used in many real-world applications: activity selection, minimum spanning tree, coin change, and scheduling problems. However, greedy doesn't always find the optimal solution, so it's important to verify when greedy works.
Key Point: Greedy algorithm makes locally optimal choice at each step, hoping for globally optimal solution. Requires greedy choice property and optimal substructure. Fast and simple, but may not find optimal solution. Works for problems where local optimal leads to global optimal.
What: Understanding Greedy Algorithm
Understanding how greedy algorithms work:
Real-Life Analogy: Making Change
Greedy algorithm is like making change with coins:
Just like making change, greedy picks the best option at each step without reconsidering.
Greedy Choice Property
Greedy choice property means locally optimal choice is part of globally optimal solution. At each step, greedy makes best choice available, and this choice is correct for final solution. Not all problems have this property. Example: Activity selection - choosing activity that ends earliest is always part of optimal solution.
Example: In coin change, picking largest coin is always correct (for US coins)
Optimal Substructure
Optimal substructure means optimal solution contains optimal solutions to subproblems. After making greedy choice, remaining problem is similar to original problem. This allows greedy to work recursively. Example: Minimum spanning tree - optimal tree contains optimal trees for subgraphs.
Example: After picking activity, remaining problem is same type (activity selection)
No Backtracking
Greedy algorithm never reconsiders previous choices. Once a choice is made, it's final. This makes greedy fast and simple, but also means it may miss optimal solution if greedy choice property doesn't hold. Greedy is "make choice and move on" approach, unlike backtracking which can undo choices.
Example: Once you pick an activity, you never reconsider it
Greedy Algorithm Flow
Greedy Decision Process
Example: Activity Selection
Important: Greedy makes locally optimal choice at each step, never reconsiders. Requires greedy choice property (local optimal is part of global optimal) and optimal substructure (optimal solution contains optimal subproblems). Greedy is fast but may not find optimal solution.
When: When to Use Greedy Algorithm
Use greedy algorithm in these situations:
Use Greedy When:
- Greedy choice property: Local optimal leads to global optimal
- Optimal substructure: Optimal solution has optimal subproblems
- Need fast solution: Greedy is efficient (O(n log n))
- Known greedy problems: Activity selection, MST, coin change
- Approximation OK: Near-optimal solution acceptable
Avoid Greedy When:
- Need guaranteed optimal: Greedy may not find optimal
- No greedy property: Local optimal doesn't lead to global
- Need to consider all: Must explore all possibilities
- Complex dependencies: Choices affect future options
- 0-1 Knapsack: Need dynamic programming, not greedy
Common Scenario: Use greedy when problem has greedy choice property and optimal substructure, and you need fast solution. Avoid greedy when you need guaranteed optimal solution or problem doesn't have greedy properties. Greedy is great for activity selection, MST, and coin change problems.
How To: Implement Greedy Algorithms with Examples
Learn to implement greedy algorithms with examples:
Example 1: Activity Selection Problem
Select maximum number of non-overlapping activities:
# Activity Selection Problem (Greedy)
# Select maximum number of non-overlapping activities
# Activities: (start, end) times
def activity_selection(activities):
# Sort activities by end time (greedy: pick activity that ends earliest)
activities.sort(key=lambda x: x[1])
selected = []
last_end = -1
for start, end in activities:
# Greedy choice: if activity doesn't overlap, select it
if start >= last_end:
selected.append((start, end))
last_end = end
return selected
# Example usage
activities = [(1, 3), (2, 5), (4, 6), (5, 7), (6, 8)]
selected = activity_selection(activities)
print(selected) # Output: [(1, 3), (4, 6), (6, 8)]
print(f"Maximum activities: {len(selected)}") # Output: 3
# How it works:
# Sort by end time: [(1,3), (2,5), (4,6), (5,7), (6,8)]
# Pick (1,3) - ends earliest
# Pick (4,6) - doesn't overlap, ends earliest
# Pick (6,8) - doesn't overlap, ends earliest
# Greedy gives optimal solution!Activity Selection Visualization
Greedy: Always pick activity that ends earliest and doesn't overlap
Example 2: Coin Change Problem (Greedy)
Find minimum coins to make amount (greedy approach):
# Coin Change Problem (Greedy)
# Find minimum coins to make amount
# Note: Greedy works for US coins, but not all coin systems!
def coin_change_greedy(coins, amount):
# Sort coins in descending order (greedy: use largest coins first)
coins.sort(reverse=True)
result = []
remaining = amount
for coin in coins:
# Greedy choice: use as many of this coin as possible
count = remaining // coin
if count > 0:
result.extend([coin] * count)
remaining -= coin * count
return result if remaining == 0 else None
# Example usage (US coins - greedy works!)
coins = [25, 10, 5, 1] # Quarters, dimes, nickels, pennies
amount = 67
result = coin_change_greedy(coins, amount)
print(result) # Output: [25, 25, 10, 5, 1, 1]
print(f"Total coins: {len(result)}") # Output: 6
# How it works:
# Use 2 quarters (25×2 = 50), remaining: 17
# Use 1 dime (10), remaining: 7
# Use 1 nickel (5), remaining: 2
# Use 2 pennies (1×2 = 2), remaining: 0
# Total: 6 coins (greedy gives optimal for US coins!)Example 3: Fractional Knapsack Problem
Maximize value with weight constraint (can take fractions):
# Fractional Knapsack Problem (Greedy)
# Maximize value, can take fractions of items
# Items: (weight, value)
def fractional_knapsack(items, capacity):
# Sort by value/weight ratio (greedy: take items with best ratio first)
items.sort(key=lambda x: x[1] / x[0], reverse=True)
total_value = 0
remaining_capacity = capacity
for weight, value in items:
if remaining_capacity >= weight:
# Take entire item
total_value += value
remaining_capacity -= weight
else:
# Take fraction of item
fraction = remaining_capacity / weight
total_value += value * fraction
break
return total_value
# Example usage
items = [(10, 60), (20, 100), (30, 120)] # (weight, value)
capacity = 50
max_value = fractional_knapsack(items, capacity)
print(f"Maximum value: {max_value}") # Output: 240.0
# How it works:
# Ratios: 60/10=6, 100/20=5, 120/30=4
# Take item 1 (ratio 6): value 60, capacity left: 40
# Take item 2 (ratio 5): value 100, capacity left: 20
# Take 2/3 of item 3 (ratio 4): value 80, capacity left: 0
# Total: 240 (greedy gives optimal for fractional knapsack!)Best Practice: Greedy makes locally optimal choice at each step. Sort items by relevant criteria (end time, value/weight ratio, etc.), then make greedy choices. Greedy is fast (O(n log n) for sorting) but verify it gives optimal solution. Works for activity selection, fractional knapsack, and MST problems.
Why: Why Greedy Algorithm Matters
Greedy algorithm matters for these reasons:
Fast and Efficient
Greedy algorithms are typically O(n log n) or O(n), making them very fast. They're much faster than dynamic programming (O(n²) or more) and backtracking (exponential). For problems where greedy works, it provides optimal or near-optimal solutions quickly.
Simple to Implement
Greedy algorithms are simple to understand and implement. The logic is straightforward: make best choice at each step. This makes greedy algorithms easy to code, debug, and maintain. Simplicity is a major advantage of greedy approach.
Common Interview Topic
Greedy algorithms are very common in coding interviews. Interviewers frequently ask about activity selection, coin change, interval scheduling, and other greedy problems. Understanding greedy algorithms is essential for technical interviews.
Real-World Applications
Greedy algorithms have many real-world applications: scheduling (activity selection), networking (minimum spanning tree), compression (Huffman coding), and resource allocation. Understanding greedy helps solve practical problems efficiently.
Important: Greedy algorithm matters because it's fast and efficient, simple to implement, is a common interview topic, and has many real-world applications. Greedy is one of the most important algorithmic techniques to understand, especially for coding interviews.
Frequently Asked Questions
What is a greedy algorithm?
Greedy algorithm makes locally optimal choice at each step, hoping it leads to globally optimal solution. Greedy chooses best option available at current moment without considering future consequences. Greedy is simple and efficient, but doesn't always give optimal solution. Greedy works when local optimal choices lead to global optimum (greedy choice property and optimal substructure).
How does greedy algorithm work?
Greedy algorithm works by: 1) Make locally optimal choice at each step, 2) Never reconsider previous choices, 3) Hope local choices lead to global optimum. Greedy is fast (O(n log n) or O(n) typically) but may not find optimal solution. Greedy is simple: just pick best option at each step. Example: coin change problem - always pick largest coin that fits.
When to use greedy algorithm?
Use greedy when: problem has greedy choice property (local optimal leads to global optimal), problem has optimal substructure (optimal solution contains optimal subproblems), need fast solution (greedy is efficient), and problem is known to work with greedy (activity selection, minimum spanning tree). Avoid greedy when: need guaranteed optimal solution, problem doesn't have greedy choice property, or need to consider all possibilities.
What is the difference between greedy and dynamic programming?
Greedy vs Dynamic Programming: Greedy makes choice and never reconsiders, DP considers all possibilities and stores results. Greedy is faster (O(n log n) typically), DP is slower (O(n²) or more). Greedy may not find optimal solution, DP finds optimal solution. Greedy is simpler, DP is more complex. Use greedy when local optimal leads to global optimal, use DP when need to consider all possibilities.
What are common greedy algorithm problems?
Common greedy problems: Activity Selection (choose maximum non-overlapping activities), Fractional Knapsack (maximize value with weight constraint), Minimum Spanning Tree (Kruskal's, Prim's algorithms), Coin Change (minimum coins for amount), Interval Scheduling (schedule maximum tasks), Huffman Coding (optimal prefix codes). These problems have greedy choice property and optimal substructure.