I have an total amount payable by an Employer this amount needs to be split amongst staff.
For example
a $100
b $200
c -$200
d -$200
e $500
The total amount payable is the sum of all items, in this case $400
The problem is I must call a 3rd party system to assign these amounts one by one. But I cannot let the balance go below $0 or above the total amount ($400) during the allocation.
So if I insert in the above order a,b,c will work so the current allocated sum = 100 + 200 - 200 = $100. However when I try to allocate d. The system will try to add -$200 which will make the current allocated sum -$100 which is < $0 which is not allowed so it will be rejected by the system.
If I sort the list so negative items are last. i.e.
a $100
b $200
e $500
c -$200
d -$200
a will work, b will work, but when it tries to insert e there will be insufficient funds error because we have exceeded the maximum of $400. I have come to the realisation that there is no silver bullet and there will always be scenarios what will break. However I wanted to come up with a solution that would work most of the time.
Normal sample of data would have between 5 - 100 items. With only 2-15% of those containing negative amounts.
Is there a clever way I can sort the list? Or would it be better just to try an allocated multiple times. For example split the positive and negatives into two list. Insert positives until one errors, then insert negatives until it errors then switch back and forth between the list until it is all allocated or until both of them error.