# Optimal stacking of bricks

I need an algorithm to optimally stack a set of bricks in a 2D plane so that the resulting wall is as vertically short as possible. Bricks are defined as a pair of integers $$(x_1, x_2)$$ corresponding to the horizontal span of $$\textit{width} = x_2 - x_1$$ and are of equal height. Bricks cannot be translated left or right, they are only allowed to "fall" in place vertically from their original horizontal position. This is conceptually similar to a game of Tetris where instead of moving bricks, the player decides the order in which they fall.

For example, in the following figure, arrangement A is the worst possible while B and C are equally optimal. The numbers inside the bricks indicate a possible stacking order.

Bricks can number in the thousands so exhaustive evaluation of all possible permutations is not conceivable.

• @greybeard - The numbers inside the bricks are meant as a possible stacking order to achieve the corresponding result. I edited the figure description to make this more explicit. Oct 25 at 19:01
• Do you need to worry about bricks toppling if unsupported? (If these were physical bricks, bricks 2, 3, and 4 in example A would fall to the right; and in example B brick 2 would fall to the left.) Oct 26 at 23:11
• @gidds - I used brick stacking order merely as a metaphor to simplify the explanation of the actual problem I'm trying to solve so I'm not interested in the mechanical behaviour of bricks. Perhaps a better metaphor would have been "minimizing the number of classrooms necessary to accommodate a schedule of classes", but the brick-based one came to mind first. Oct 27 at 1:46