Slot Fill Algorithm

Question

I am looking for an algorithm to fill several slots that are already filled to some level.

• The current levels and the amount available for filling are known.
• The resulting levels should be as equal as possible, but the existing level cannot be reduced.
• Slots are filled from left to right, so left slots get a higher level if it is impossible to achieve an equal level.

      Examples http://img695.imageshack.us/img695/6529/fill.png

The above figure shows six examples, each column is a slot. The gray area is already filled, blue is the expected position of the new elements.

---

I could iterate through my slots and increase the quantity in the lower slot by 1until the quantity is consumed, but I am wondering how to actually calculate the new fill levels.

I'm going to implement this with SQL/ PL/SQL, other code is also welcome :)

Answer 1

It is pretty simple.

You can visualize this as pouring water and filling it, except in certain cases *.

• Sorting. You can also use the priority queue.
• Keep track of the number of current minute columns.
• Get the min column with the second min column.
• min , min.
• .
• 4 , , ( - ), . , ( ), , .
• , , 6.

.

O( n log n ) .

* , :

 #
 #
##
###
###

, , , , , .

Answer 2

, .

n - , .

1: , . , .

2: 1, , .

3: n = n-1

1, 2 3 n = 0 .

Answer 3

• .
• ().
• , , . , .
• i, . ( , №3 i), floor(remaining / i) remaining % i.
• , .

, ( ).

Answer 4

Sounds like a classic. Backpack problem. There are a number of different language solutions for this that use different algorithms in Rosetta Code , although I'm not sure if anything is in PL / SQL