Subj : Re: stacking algorithm
To   : comp.programming
From : Omri Barel
Date : Thu Aug 04 2005 10:19 am

nobiscuit wrote:
> Hi,
> 
> I need some pointers on a good place to start with an algorithm to
> solve this problem.
> 
> Given an arbitrary collection of lines with differing 'lengths' and
> starting points - like this:
> 
> ---------   (length = 9, start = 0)
>   ---       (length = 3, start = 2)
> --          etc
> -----------
>     -----
>        -----
> ---
> 
> 
> And a fixed width 'tray' to place them in, like this:
> 
> 
> |____________|  (length = 12)
> 
> 
> 
> I need to find a way to 'stack' them in a reasonably efficient way -
> like this:
> 
> 
> (Gaps in between lines shown for clarity)
> 
>  --- -----
>  -- ---	-----
>  ---------
>  -----------
> |____________|  TRAY
> 
> 
> The code I inherited just checks the starting point of the current line
> being processed against the ending point of the previous line being
> processed and if there is overlap it moves the current line up a level
> in the stack.  This creates situations like this:
> 
>           ------
>     ----------
> --------
> 
> The requirements team wants something like this instead:
> 
>     ----------
> --------  ------
> 
> 
> 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?
> 
> Thanks!
> 

Let's think about this one for a moment. Each two lines can either "sit 
together" or not (they don't if they overlap). So you could create a 
graph which describes your situation: the nodes are your lines, and an 
edge exists between v and u if v and u can "sit together".

A clique in the graph is a set of lines which can all "sit together". 
Note that anything else is not good - if A can sit with B, and B with C, 
but C can't sit with A then they cannot "sit together".

And now we've reduced the problem to finding a minimum clique partition 
of the graph, which is an NP problem:

http://www.nada.kth.se/~viggo/wwwcompendium/node25.html

Hope this gives you some direction... (you may wish to look at clique 
partitions which aren't minimal).

.