Chapter 8: Greedy Algorithms

1. Greedy Algorithm Fundamentals

Greedy Strategy

1. Make greedy choice: Choose the best option at current step
2. Reduce problem: Solve smaller subproblem
3. No backtracking: Once choice is made, don't reconsider

When Greedy Works

• Greedy choice property: Optimal solution contains greedy choice
• Optimal substructure: Optimal solution to subproblem is part of optimal solution

2. Activity Selection Problem

Example: Maximum Non-Overlapping Activities

Problem: Select maximum number of activities that don't overlap.

def activity_selection(activities):
    """
    Select maximum non-overlapping activities.
    
    Args:
        activities: List of (start, end) tuples
    
    Returns:
        List of selected activity indices
    """
    # Step 1: Sort activities by end time
    # Greedy choice: always pick activity that ends earliest
    sorted_activities = sorted(enumerate(activities), key=lambda x: x[1][1])
    
    selected = []
    last_end = -1
    
    # Step 2: Greedily select activities
    for idx, (start, end) in sorted_activities:
        # Step 3: Check if activity doesn't overlap
        if start >= last_end:
            # Step 4: Select this activity
            selected.append(idx)
            # Step 5: Update last end time
            last_end = end
    
    return selected

3. Jump Game

Example: Can Reach End

Problem: Can you reach the last index? (nums[i] = max jump from position i)

def can_jump(nums):
    """
    Check if can reach last index using greedy approach.
    
    Args:
        nums: List where nums[i] is max jump from position i
    
    Returns:
        True if can reach last index, False otherwise
    """
    # Step 1: Track farthest reachable position
    max_reach = 0
    
    # Step 2: Iterate through array
    for i in range(len(nums)):
        # Step 3: Check if current position is reachable
        if i > max_reach:
            # Can't reach current position
            return False
        
        # Step 4: Update farthest reachable position
        # From position i, can reach i + nums[i]
        max_reach = max(max_reach, i + nums[i])
        
        # Step 5: Early termination
        # If can already reach end, return True
        if max_reach >= len(nums) - 1:
            return True
    
    return True

4. Minimum Coins (Greedy - When It Works)

Example: Greedy Coin Change

Note: Greedy only works for certain coin systems (e.g., US coins).

def coin_change_greedy(coins, amount):
    """
    Greedy coin change (only works for certain systems).
    
    Args:
        coins: List of coin denominations (sorted descending)
        amount: Target amount
    
    Returns:
        Minimum number of coins, or -1 if impossible
    """
    # Step 1: Sort coins in descending order
    coins.sort(reverse=True)
    
    count = 0
    
    # Step 2: Greedily use largest coins first
    for coin in coins:
        # Step 3: Use as many of this coin as possible
        if amount >= coin:
            num_coins = amount // coin
            count += num_coins
            amount -= num_coins * coin
        
        # Step 4: Early termination
        if amount == 0:
            break
    
    # Step 5: Check if solved
    return count if amount == 0 else -1

📚 Chapter Summary

• Greedy Strategy: Make locally optimal choice at each step
• When it works: Greedy choice property + optimal substructure
• Common patterns: Sort first, then make greedy choices
• Activity Selection: Sort by end time, pick earliest ending
• Jump Game: Track farthest reachable position

Key Takeaway: Greedy is efficient but only works when locally optimal choices lead to globally optimal solution. When in doubt, verify with proof or use DP.