Find a way to minimize max difference

Question

N people needs different amount of money given by : X_i (1<=i<=N) But we have a fixed money denoted by M. It may happen that M is less than the total money which is required to fulfill everyone's need.

I want to find a way to distribute the money (M) such that the maximum difference between the required money and given money is minimize over all the people. Is there a way to do that?

  e.g : N = 4, M=3

  X1=5, X2=4, X3=2, X4=2

  In this case we should distribute like : 2 1 0 0 
  so difference array is : 3 3 2 2
  maximum difference is minimized (which is 3) 

Any interesting link are also welcome on this topic.

Answer 1

This can be solved in a single pass after ordering the amounts of debt descendingly. Debt is paid from top to bottom. This python code should make it clear:

def get_max_debt_after_distribution(debt, money):

    if not debt:
        raise ValueError('Please specify debt')

    debt.sort(reverse=True)
    debt.append(0)  # Add zero debt to simplify algorithm

    for i in range(1, len(debt)):
        last_amount = debt[i-1]
        new_amount = debt[i]

        # To bring the max diff down from "last_amount" to "new_amount",
        # we need to pay the difference for each debt
        to_pay = (last_amount - new_amount) * i

        # Check if we have enough money to pay the full amount
        if to_pay <= money:
            money -= to_pay
        else:
            # Out of money. Remaining money goes to highest debts.
            return last_amount - int(money / i)

    # There was enough money to pay all the debt
    return 0

print(get_max_debt_after_distribution([5, 4, 2, 2], 3))  # prints 3
print(get_max_debt_after_distribution([5, 5, 5, 5], 7))  # prints 4