Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public static List<Settlement> simplifyDebts(Map<String, Double> netBalances) {
- // Max-heap for creditors
- PriorityQueue<UserBalance> creditors = new PriorityQueue<>(
- (a, b) -> Double.compare(b.amount, a.amount)
- );
- // Min-heap for debtors
- PriorityQueue<UserBalance> debtors = new PriorityQueue<>(
- Comparator.comparingDouble(a -> a.amount)
- );
- // Divide users into creditors and debtors
- for (Map.Entry<String, Double> entry : netBalances.entrySet()) {
- if (entry.getValue() > 0) {
- creditors.add(new UserBalance(entry.getKey(), entry.getValue()));
- } else if (entry.getValue() < 0) {
- debtors.add(new UserBalance(entry.getKey(), entry.getValue()));
- }
- }
- List<Settlement> settlements = new ArrayList<>();
- while (!creditors.isEmpty() && !debtors.isEmpty()) {
- UserBalance creditor = creditors.poll();
- UserBalance debtor = debtors.poll();
- double settlementAmount = Math.min(creditor.amount, -debtor.amount);
- settlements.add(new Settlement(debtor.user, creditor.user, settlementAmount));
- creditor.amount -= settlementAmount;
- debtor.amount += settlementAmount;
- // Push them back if there's remaining balance
- if (creditor.amount > 0) creditors.add(creditor);
- if (debtor.amount < 0) debtors.add(debtor);
- }
- return settlements;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
