Payroll Distribution

  # ----------------------------------------
  # 1. Payroll Distribution - Proportional Allocation
  #
  # Problem: Gusto has a payroll to distribute. Given the amount of current funds
  # and a hash of recipients, calculate the fair distribution of funds.
  #
  # Rules:
  # - If sufficient funds: pay everyone in full
  # - If insufficient funds: distribute proportionally
  # - Handle remainder fairly using highest fractional parts
  #
  # Examples:
  # amount = 40, recipients = {a: 10, b: 5, c: 10, d: 8}
  # Output: {a: 10, b: 5, c: 10, d: 8} (full payment)
  #
  # amount = 30, recipients = {a: 10, b: 5, c: 10, d: 8}
  # Output: {a: 9, b: 5, c: 9, d: 7} (proportional with remainder distribution)
  #
  # Time Complexity: O(n log n) due to sorting for remainder distribution
  # Space Complexity: O(n)
  # ----------------------------------------
  def distribute_payroll(amount, recipients)
    return {} if recipients.empty? || amount <= 0
    
    total_owed = recipients.values.sum
    puts "Total owed: #{total_owed}, Available funds: #{amount}"
    
    # If we have enough funds, pay everyone in full
    if amount >= total_owed
      puts "Sufficient funds - paying everyone in full"
      return recipients.dup
    end
    
    # Calculate proportional distribution
    result = {}
    distributed = 0
    fractional_parts = []
    
    puts "\nCalculating proportional distribution:"
    recipients.each do |name, owed|
      exact_proportion = (amount * owed) / total_owed.to_f
      base_amount = exact_proportion.floor
      fractional_part = exact_proportion - base_amount
      
      result[name] = base_amount
      distributed += base_amount
      fractional_parts << [name, fractional_part]
      
      puts "#{name}: owed=#{owed}, proportion=#{exact_proportion.round(3)}, base=#{base_amount}, fractional=#{fractional_part.round(3)}"
    end
    
    # Distribute remainder based on highest fractional parts
    remainder = amount - distributed
    puts "\nRemainder to distribute: #{remainder}"
    
    if remainder > 0
      # Sort by fractional part (descending) to give remainder fairly
      fractional_parts.sort_by! { |_, frac| -frac }
      
      puts "Distributing remainder to recipients with highest fractional parts:"
      remainder.times do |i|
        name = fractional_parts[i][0]
        result[name] += 1
        puts "  +1 to #{name} (fractional part: #{fractional_parts[i][1].round(3)})"
      end
    end
    
    puts "\nFinal distribution: #{result}"
    puts "Total distributed: #{result.values.sum}"
    result