Algorithm to fill slots

Question

I am searching for an algorithm to fill several slots, which are already filled to some level.

• The current levels and the available quantity to fill are known
• Resulting levels should be as equal as possible, but existing level cannot be reduced
• Slots are filled from left to right, so left slots get higher level if equal level is impossible

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

The image above shows six examples, each column represents a slot. The grey area is already filled, the blue are is the expected position of the new elements.

---

I could iterate through my slots and increase the quantity on the lowest slot by 1 until the available quantity is consumed, but I wonder about how to actually calculate the new filling levels.

I am going to implement this with SQL/PL/SQL, other code is just as welcome though :)

Answer 1

This is pretty straightforward.

You can visualize this as pouring water and let it fill, except for certain cases *.

1. Sort. You can also use a priority queue.
2. Keep track of the number of current min columns.
3. Get the min column with the second min column.
4. Fill the min column with either the number of available items, or up to the second min column.
5. Increment the count of current min columns.
6. Go to step 4 until all columns are at the same level, except use the number of available items, or delta (second min - first min ) times the number of current min columns. If the number of available items is not enough, just do simple math (division and remainder) to fill the columns, and use the remainder to fill from the left.
7. When all the columns are on the same level, use the simple math part described in step 6.

You should be good.

This algorithm runs in O( n log n ) time.

*Some cases this doesn't make sense, but you would still want to do it anyhow:

 #
 #
##
###
###

In that case, you would fill the third column, then the first, then the second, but of course it's not quite filling water.

Answer 2

Perhaps a greedy algorithm with randomization to break ties will be sufficient.

Let n be the number of slots you need to fill.

Step 1: Loop through the columns to identify the columns that have the least no of filled up slots. Skip the columns that are already filled up.

Step 2: If no of columns are identified in step 1 is greater than one then choose one at random.

Step 3: Set n = n-1

Repeat steps 1, 2 and 3 till n = 0 or you do not have any empty columns.