Greedy Algorithms

Definition

A Greedy Algorithm is a problem-solving approach where you make the “best” choice available right now (the local optimum), hoping it leads to the best overall solution (the global optimum). It never looks back or changes a previous decision.

How it Works

1. Selection: At every step, look at all available options.
2. Greedy Choice: Pick the one that offers the most immediate benefit.
3. Repeat: Move to the next step and do it again until the problem is solved.

Note: Greedy algorithms don’t work for every problem, but when they do, they are incredibly fast.

Real-World Analogy

Counting Cashier: Imagine you are a cashier and you need to give a customer $67 in change using the fewest bills possible.

• You grab a $50 bill first (Greedy choice: largest value). Remaining: $17.
• You grab a $10 bill next. Remaining: $7.
• You grab a $5 bill. Remaining: $2.
• You grab two $1 bills.
• You didn’t consider giving three $20s and seven $1s. You just greedily took the biggest bill that fit.

Example

Problem: Activity Selection. You have meetings with start and end times. Select the maximum number of meetings a single person can attend (they cannot overlap).

Meetings: (1-3), (2-4), (3-5), (0-6)

Logic: Sort by finish time. Pick the one that finishes earliest so you have time for more.

1. Pick (1-3). Ends at 3.
2. Next available is (3-5).
3. Total: 2 meetings.

Code Example (Python)

def make_change(amount, coins):
    coins.sort(reverse=True) # Always pick largest first
    result = []
   
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
           
    return result

print(make_change(67, [1, 5, 10, 25, 50]))
# Output: [50, 10, 5, 1, 1]

Complexity Analysis

• Time Complexity: O(N log N) (Usually dominated by sorting the input first).
• Space Complexity: O(1) usually, as it doesn’t store previous states.

Use Cases

• Data Compression: Huffman Coding (used in ZIP files).
• Networking: Dijkstra’s Algorithm (finding the shortest path).
• Scheduling: Allocating resources.