Subj : Re: stacking algorithm
To   : comp.programming
From : googmeister
Date : Sun Aug 07 2005 05:06 am

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?

I'm not entirely sure I understand your problem correctly,
but it seems to be essentailly be "Interval Partitioning"
(at least if there are no "center-of-mass" constraints on
how you're allowed to stack the intervals so they don't
topple).

Interval Partitioning: given n intervals (ai, bi), assign them
to the minimum number of levels so that no two intersect.

Interval Partitioning has an optimal greedy solution:
Consider the intervals in ascending order of left endpoint.
Assign the interval to any existing level to the lowest level
to which it is compatible (creating a new level if no such
existing level exists). The algorithm can be implemented
in O(n log n) time by sorting and maintaining a priority
queue of the rightmost endpoints of the intervals in each level.

By assigning them in increasing order of level, you ensure
that every interval intersects an interval in the level beneath it.

.