Greedy Algorithms: The Short-Sighted Hunter

The Story: The Coin Collector

Imagine you are a cashier. A customer needs 41 cents in change. You have coins for 25, 10, 5, and 1 cent. How do you give the change using the fewest number of coins?

Naturally, you take the biggest coin that fits first:

1. Take a 25¢ coin (Remaining: 16¢)
2. Take a 10¢ coin (Remaining: 6¢)
3. Take a 5¢ coin (Remaining: 1¢)
4. Take a 1¢ coin (Remaining: 0¢)

Total: 4 coins. This “Take the biggest first” strategy is a Greedy Algorithm. You didn’t think about the future; you just grabbed the best thing right now. For many currency systems, this greedy choice is actually the optimal choice.

Why do we need it?

• Speed: Greedy algorithms are usually $O(N)$ or $O(N \log N)$. They are much faster than DP.
• Networking: Dijkstra’s algorithm (Shortest Path) and Prim’s algorithm (Minimum Spanning Tree) are both greedy.
• Compression: Huffman coding uses a greedy strategy to build the optimal tree.
• Scheduling: Fitting the maximum number of meetings into a single room.

How the Algorithm “Thinks”

The algorithm is a Sequential Decision Maker.

1. Selection: Pick the “Best” candidate from the current set.
2. Feasibility: Check if this candidate violates any rules.
3. Irreversibility: Once you pick a candidate, you never go back. There is no “Undo” button in Greedy.

The Greedy Choice Property: A greedy algorithm only works if a local optimum leads to a global optimum.

• The Trap: If you had coins for 25, 20, and 1 cent, and you needed 40 cents change…
  • Greedy: 25 + 1 + 1… (16 coins)
  • Reality: 20 + 20 (2 coins) In this case, the short-sighted hunter fails.

Engineering Context: The “Good Enough” Solution

In many complex engineering problems (like the Traveling Salesperson Problem), finding the perfect answer takes years.

• Engineers often use Greedy Heuristics to find an answer that is “95% perfect” in 10 milliseconds.
• In production, a fast, good answer is often better than a slow, perfect one.

Implementation (Python)

# Interval Scheduling: Fitting maximum meetings into one room
def schedule_meetings(meetings):
    # meetings = [(start, end), ...]
    
    # 1. Greedy Choice: Sort meetings by END time
    # The sooner a meeting ends, the more room we have for others.
    meetings.sort(key=lambda x: x[1])
    
    count = 0
    last_end_time = 0
    selected = []

    for start, end in meetings:
        if start >= last_end_time:
            # 2. Feasibility: Does it overlap? No.
            count += 1
            last_end_time = end
            selected.append((start, end))
            
    return count, selected

# Usage
mtgs = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11)]
print(f"Max Meetings: {schedule_meetings(mtgs)}")

Summary

Greedy Algorithms teach us that sometimes, focus is better than planning. By ruthlessly pursuing the best immediate option, we can solve complex problems with minimal effort. It reminds us that while we should strive for the best possible outcome, we must also respect the cost of time and complexity.