11
$\begingroup$

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.

enter image description here

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

$\endgroup$
3
  • $\begingroup$ @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. $\endgroup$
    – pmjobin
    Oct 25 at 19:01
  • $\begingroup$ 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.) $\endgroup$
    – gidds
    Oct 26 at 23:11
  • $\begingroup$ @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. $\endgroup$
    – pmjobin
    Oct 27 at 1:46
18
$\begingroup$

Consider a graph whose vertices are the intervals, and whose edges correspond to intersecting intervals. This is an example of an interval graph.

In a solution, all intervals on a given row of the solution are non-intersecting. Therefore, if we color each interval according to the line it is on, we get a valid coloring of the graph. Conversely, given a valid coloring of the graph, we get a solution to your problem whose height is the number of different colors: simply drop all intervals colored 1, then all intervals colored 2, and so on.

In other words, your problem is equivalent to interval graph coloring, which can be solved efficiently.

$\endgroup$
4
  • 9
    $\begingroup$ And for posterity, the efficient solution referred to is to sort the intervals by their left endpoint, then just iterate through them giving them each the smallest legal color. $\endgroup$ Oct 25 at 18:13
  • $\begingroup$ @yuval-filmus is it wrong to assume the problem can be reduced to packing the most number of bricks (packing the bricks such that gap between each brick in a row is minimal) in each row? $\endgroup$
    – Node.JS
    Oct 26 at 4:56
  • $\begingroup$ I don’t know. You can try to prove or refute this conjecture. It’s probably wrong. $\endgroup$ Oct 26 at 4:58
  • 1
    $\begingroup$ @Node.JS: Minimizing the total number of rows is equivalent to maximizing the average (arithmetic mean) number of bricks per row (since the total number of rows is the total number of bricks divided by the average number of bricks per row); but it doesn't seem a-priori easier to maximize the average number of bricks per row than to minimize the total number of rows . . . $\endgroup$
    – ruakh
    Oct 27 at 2:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.