465. Optimal Account Balancing

465. Optimal Account Balancing

A group of friends went on holiday and sometimes lent each other money. For example, Alice paid for Bill's lunch for $10. Then later Chris gave Alice $5 for a taxi ride. We can model each transaction as a tuple (x, y, z) which means person x gave person y $z. Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person's ID), the transactions can be represented as [[0, 1, 10], [2, 0, 5]].

Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.

Note:

1. A transaction will be given as a tuple (x, y, z). Note that x ≠ y and z > 0.
2. Person's IDs may not be linear, e.g. we could have the persons 0, 1, 2 or we could also have the persons 0, 2, 6.

Example 1:

Input:
[[0,1,10], [2,0,5]]

Output:
2

Explanation:
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.

Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.

Example 2:

Input:
[[0,1,10], [1,0,1], [1,2,5], [2,0,5]]

Output:
1

Explanation:
Person #0 gave person #1 $10.
Person #1 gave person #0 $1.
Person #1 gave person #2 $5.
Person #2 gave person #0 $5.

Therefore, person #1 only need to give person #0 $4, and all debt is settled.

------------------------
ToDo*再研究⼀下
dfs 返回的是 [i, end]这⼀段所最⼩小交易易数
参考http://www.mathmeth.com/tom/files/settling-debts.pdf 题意求最少的交易易次数。

class Solution {
    public int minTransfers(int[][] transactions) {
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int[] i : transactions) {
            map.put(i[0], map.getOrDefault(i[0], 0) + i[2]);
            map.put(i[1], map.getOrDefault(i[1], 0) - i[2]);
        }
        
        List<Integer> debts = new ArrayList<>(map.values());
        return dfs(debts, 0); // 为什么选0？
    }
    
    private int dfs(List<Integer> debts, int start) {
        while (start < debts.size() && debts.get(start) == 0) {
            start++; // 遇到0后继续往下
        }
        
        if (start == debts.size()) return 0;
        int rt = Integer.MAX_VALUE;
        
        for (int i = start + 1; i < debts.size(); i++) {
            if (debts.get(start) * debts.get(i) < 0) {
                debts.set(i, debts.get(i) + debts.get(start));
                rt = Math.min(rt, 1 + dfs(debts, start + 1));
                debts.set(i, debts.get(i) - debts.get(start));
            }
        }
        
        return rt;
    }
}

变种：发现帐号不平衡后，怎么去平均
找一个中间人（可以为任意的人），其他人都给他转钱或取钱。
follow-up：优化。2种方法
1. 最少交易次数（就是LC这题了）
2. 最少交易额度, 预处理之后，用中间人的算法

from above ref:
1. generality (arbitrary number of lenders),
2. simplicity and practical feasibility,
3. minimized total amount transferred,
4. minimized total number of transfers, and
5. mathematical complexity of obtaining a solution.
There are, however, many other issues that might be considered, such as
1. charging interest on loans,
2. handling exchange rates for multiple currencies, and
3. dealing with distrust among the lenders.