1
$\begingroup$

Similar to the classic 2D strip packing problem, we want to put N blocks into a 2d strip and minimize the height of the strip. Each block has to be put at the fixed x-coordinate. The width and height of all blocks are integer.

Below is an example of 4 blocks:

you can only move every block up and down to reduce the overrall height. And a possible solution can be:

This problem originated from a memory allocation problem. For a computer, there are N known processes. Their start time and memory usage are different. We need to allocate memory properly to minimize the peak memory usage.

Does anyone have any clue to solve this problem?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

I think this is the same as the register allocation problem, so I would guess that you might be able to use the same techniques.

Improve this answer
$\endgroup$
0
$\begingroup$

This is equivalent to the problem of finding the chromatic number of an interval graph. This can be done by a greedy algorithm: sort the blocks in ascending order (after left endpoint) and, for each block, put it on the lowest level where there is room for it.

Improve this answer
$\endgroup$
1
  • $\begingroup$ thanks! It is a nice problem transformation : ) $\endgroup$
    – Xiaotian Hu
    Commented Dec 27, 2023 at 9:59

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.