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.

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.

StackExchange Computer Science Q#145083, answer score: 18