greedy algorithm for settling up

settle-up.py

def minimize_transactions(balances):
    """
    balances: dict of {person: net_balance}
    Returns: list of (from, to, amount) transactions
    """
    transactions = []
    credits = {p: b for p, b in balances.items() if b > 0}
    debts = {p: -b for p, b in balances.items() if b < 0}
    
    while credits and debts:
        max_credit_person = max(credits, key=credits.get)
        max_debt_person = max(debts, key=debts.get)
        
        amount = min(credits[max_credit_person], debts[max_debt_person])
        
        transactions.append((max_debt_person, max_credit_person, amount))
        
        credits[max_credit_person] -= amount
        debts[max_debt_person] -= amount
        
        if credits[max_credit_person] == 0:
            del credits[max_credit_person]
        if debts[max_debt_person] == 0:
            del debts[max_debt_person]
    
    return transactions