Greedy Algorithms

Greedy Algorithms

# Make locally optimal choice at each step
# Prove it leads to globally optimal solution

# Activity Selection -- max non-overlapping intervals
def max_activities(intervals):
    intervals.sort(key=lambda x: x[1])  # sort by end time
    count, last_end = 0, float('-inf')
    for start, end in intervals:
        if start >= last_end:
            count   += 1
            last_end = end
    return count

# Jump Game -- can you reach end?
def can_jump(nums):
    max_reach = 0
    for i, jump in enumerate(nums):
        if i > max_reach: return False
        max_reach = max(max_reach, i+jump)
    return True

# Minimum coins
def min_coins(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        count  += amount // coin
        amount %= coin
    return count if amount==0 else -1
    # Note: greedy only works for canonical coin systems
    # Use DP for general case

# Huffman coding -- greedy for optimal compression
# Prim's MST -- greedy edge selection