You own a bank and want to maximize the overdraft fees you collect. For each overdrafted transaction you get a $25 profit. Given the withdrawals made on one day for an account, a bank is not required to process the withdrawals based on the time they took place. Instead, a bank is allowed to arrange the withdrawals made on one day in any order.
How should the withdrawals be arranged to maximize your bank’s profit?
If the account has funds for all withdrawals, the order does not matter (the bank gets no overdraft fees). If the account does not have a high enough balance, the strategy should be to drain the account as soon as possible and to maximize the number of overdraft fees the bank can collect. Hence, the bank will
- sort the withdrawals from largest transactions to smallest
- scan the sorted list and determine the transactions with no overdraft fee and the ones with an overdraft fee
For example, consider an account with a balance of $100 and withdrawals of 2, 70, 15, 5, 3, 4, 25. The withdrawals total to $124.
- If withdrawals are processed in the given order, only the last withdrawal faces an overdraft fee and the penalty is $25.
- If the bank is allowed to sort the withdrawals, 70 and 25 are processed first and the third withdrawal of $15 already has an overdraft fee. The daily transactions will encounter a total of 5 overdraft fees costing the individual $125. US banks were allowed to do this until a few years ago.
Program: Algorithms_1_overdraft.py
The program includes a function computing the penalty when the transactions are processed in order they took place and a second function computing the penalty when the transactions are sorted from largest to smallest and then processed. The program also computes and prints the bank’s profit.
Additional discussion topics
- Let students come up with other tasks or activities in everyday life or in businesses where sorting plays a natural role.
- Related: penny shaving – http://en.wikipedia.org/wiki/Salami_slicing – make money from consumers by rounding to the nearest cent.
