We discusse the problem of settling balances between six users and designing a payment graph to minimize the number of transactions.
The approach involves taking the largest positive and negative balances and eliminating them by making a transaction between them.
The data structure used is a heap, and the greedy approach is not optimal but has some advantages. We also show that a simple approach may not always be the best solution with an example.
Simplified Balances algorithm
5 mins