有效共享费用后偿还债务:每人最多交易1笔

上下文

我正在创建一个程序来简化人与人之间的共享费用.费用有:

最初支付费用的付款人
一些贡献者,他们将支付一部分费用(注意付款人也是贡献者)

捐助者必须为某项费用支付的股份不一定必须相等.经过一些任意数量的开支后,有些人会欠钱,而其他人欠钱.

问题

问题是找到一个让所有人解决债务的简单方法.我想要一个人最多支付另一个人的费用,而不是某些人不得不支付其他几个人,而有些人根本不需要支付任何费用.此外,我想尽量减少一个人收到的超出他或她实际欠款的金额.例如,如果你欠100美元,你真的不想收到2000美元,并且必须向其他人转发1900美元.

模型

每个人都有债务.债务是:

如果这个人欠钱就是积极的
如果该人欠款,则为负数
零,如果以上都不是

因此,该模型由一组数字组成,代表债务.

这是一个零和的情况:人们所欠的钱数等于人们所欠的钱数(没有贷款人就没有贷款).这意味着无论谁收到付款,如果最后每个人都支付了欠款,就没有人欠任何钱.

安妮支付鲍勃100美元.如果安妮有100的债务,她的债务现在为0.如果鲍勃的债务为-100,他的债务也是0.在该模型中,货币交易相当于从付款人的债务中扣除,并添加相同的债务相当于收件人的.

为了最大限度地减少交易中收款人的超额收款,我认为将最大的正债务加到每笔交易的最大负债中应该足够了.

履行

我正在考虑为负债使用最小堆,为正债使用最大堆.然后重复执行从最大最大到最小最小的事务.这可以通过将min的键增加最大值并删除max来完成.如果债务为零,则将其从堆中删除.

伪代码

让我们max成为最大元素maxHeap和min最小元素minHeap.max.person和min.person是谁持有的债务的人max,并min分别.

while(not done) do:
    new transaction.from(max.person).to(min.person)
    if(max + min = 0) then:               //remove both
        maxHeap.removeMax
        minHeap.removeMin
    else if (max + min < 0) then:         //keep in minHeap
        minHeap.increaseKey(min).by(max)
        maxHeap.removeMax
    else                                  //move min to maxHeap
        maxHeap.decreaseKey(max).by(|min|)

Run Code Online (Sandbox Code Playgroud)

如果我没弄错的话,这应该给我O(nlogn)的运行时间.