views:

20

answers:

0

The abstraction of my problem is that in a cartesian plane there are a lot of rectangles. These rectangles have known integer sizes and must have integer coordinates(their abscissas are known and fixed, only their ordinates may vary).

The problem is to find those ordinates for which the smallest rectangle that contains all the given rectangles is minimum. This means that it should have minimum height, since its width is fixed because the small rectangles have fixed abscissas.

I don't know if i should use backtracking or there is a faster way, i can imagine that at 50 rectangles it would take some measurable time to compute the correct solution and a greedy algorithm doesn't sit well with me.