Subj : Re: stacking algorithm
To   : comp.programming
From : Omri Barel
Date : Thu Aug 04 2005 01:45 pm

Jon Harrop wrote:
> nobiscuit wrote:
> 
>>I figure this has to be a pretty common problem.  I did a google search
>>but didn't find anything.  Can anyone suggest an algorithm which is
>>similar or does anyone have any cunning suggestions for an algorithm?
> 
> 
> It isn't too cunning, but what about trying to insert each line in turn into
> the current stack + one empty line?
> 

....

The result is not necessarily minimal. You insert the line segment into 
the first line it can fit in (and on top otherwise).

Let's take these lines (in order):

xx
xxxxx
       xxx
    xxxxxx

The minimal solution is:

xxxxx xxx
xx xxxxxx

Your algorithm produces:

    xxxxxx
xxxxx
xx    xxx

Which is not minimal.

(The lines in the solution may be reversed - I stacked mine from the 
bottom).

.