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.

Improve this question
$\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
    Commented Oct 25, 2021 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
    Commented Oct 26, 2021 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
    Commented Oct 27, 2021 at 1:46

1 Answer 1

Reset to default
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 reducible to interval graph coloring, which can be solved efficiently.

Improve this answer
$\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$
    – Daniel Wagner
    Commented Oct 25, 2021 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
    Commented Oct 26, 2021 at 4:56
  • $\begingroup$ I don’t know. You can try to prove or refute this conjecture. It’s probably wrong. $\endgroup$
    – Yuval Filmus
    Commented Oct 26, 2021 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
    Commented Oct 27, 2021 at 2:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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