Fairly Distribute Money With Limits

Fairly Distribute Money With Limits

You are tasked with distributing a total amount of money total among n recipients. Each recipient has a specific limit which represents the maximum amount of money they are allowed to receive. Your goal is to distribute the money as evenly as possible.

Specifically, follow these rules:

1. No recipient can receive more than their limit.
2. The distribution should be as "fair" as possible: if you have leftover money after distributing an initial amount, you must distribute the remainder by giving 1 unit to the recipient who currently has the least amount and is below their limit, until the money runs out.
3. Return an array of size n representing the amount each recipient receives.

Function Signature

def distribute_money(total: int, limits: List[int]) -> List[int]:

Constraints

• 1 <= total <= 10^9
• 1 <= n <= 10^5
• 1 <= limits[i] <= 10^9

Example 1

Input: total = 10, limits = [3, 3, 3] Output: [3, 3, 3] (with 1 leftover, which cannot be assigned as everyone is at their limit)

Example 2

Input: total = 7, limits = [2, 5, 4] Output: [2, 3, 2]

Explanation: Start by giving everyone an equal share or filling based on limits. In this case, 7 is split to ensure no one exceeds their limit while keeping the difference between recipients minimal.