Packing maximum-size rectangles with one dimension fixed

Question

I am trying to find a polynomal algorithm to solve the following problem at least approximately (I’m not sure whether the problem might be NP-hard):

Given a set of open intervals on the real line, one shall "extend" these into the second dimension, creating a set of rectangles, and pack these into a strip of heigth 1, that is R x [0,1].

The solution shall try to avoid rectangles of small height – in formal terms the ascendingly sorted vector of rectangle heights shall be maximal in regard to lexical comparison.

Example solution for the given problem (0, 3) red, (1, 5) green, (3, 7) purple, (4, 6) blue:

Another slightly more complex example: (0, 1), (0, 6), (1, 2), (1, 8), (3, 9), (4, 5), (7, 8), (8, 9)

The second solution is actually not optimal: If grey and cyan were swapped, blue could be grown to height 2/4 at the cost of shrinking purple to height 2/4 - a better solution.

Answer 1

This does have an NP-complete feeling about it.

You can certainly come up with a random solution by assigning the n intervals to line segments at randomly chosen heights from (1/n, 2/n, ... 1) and then expanding/sliding the intervals vertically until it can't grow any more. Do that a few times and the best solution is probably going to be OK. You can then throw simulated annealing at it to iteratively improve good random solutions to even better ones.

Another approach is to figure out the maximum number m of intervals open at the same time. Then progress from left to right and randomly assign intervals to currently open slots of size 1/m. Then expand/slide intervals as before to find a locally maximal solution. Unlike the first, this is going to guarantee that the shortest rectangles are the best size. As before, you can use this generation method as the start of a random optimization algorithm.