Hi, I've been sitting here for a while now thinking about a problem. It basically goes like this:

You receive a number of building blocks, they have all got both a height and a width. You may not put a wider block on top of a smaller one. And you may not put a shorter block on top of a taller one. The number of blocks can get very big and I am just finding it really hard to find a way of solving this in a way which does not take way to long. So if you have an idea of how this could possibly be done, please give me a hint so that I can feel better about myself :D!

Thanks!

> The number of blocks can get very big

>¿how much?

>¿what problem do you want to solve?

>by the way, ¿width >= height? ¿may rotate blocks?

Yes, sorry, there is one level up to (100000) blocks and one up to (500) in under 3 sec.

I want to find the largest possible height.

And no, no rotation allowed :).

And also height >= last height. whilst width < last width

You receive a number of building blocks, they have all got both a height and a width. You may not put a wider block on top of a smaller one. And you may not put a shorter block on top of a taller one. The number of blocks can get very big and I am just finding it really hard to find a way of solving this in a way which does not take way to long. So if you have an idea of how this could possibly be done, please give me a hint so that I can feel better about myself :D!

Thanks!

> The number of blocks can get very big

>¿how much?

>¿what problem do you want to solve?

>by the way, ¿width >= height? ¿may rotate blocks?

Yes, sorry, there is one level up to (100000) blocks and one up to (500) in under 3 sec.

I want to find the largest possible height.

And no, no rotation allowed :).

And also height >= last height. whilst width < last width

Last edited on

> The number of blocks can get very big

¿how much?

> and I am just finding it really hard to find a way of solving this

¿to solve what? ¿do you want to maximize the number of blocks used? ¿the area covered? ¿create the highest tower?

¿what problem do you want to solve?

by the way, ¿width >= height? ¿may rotate blocks?

¿how much?

> and I am just finding it really hard to find a way of solving this

¿to solve what? ¿do you want to maximize the number of blocks used? ¿the area covered? ¿create the highest tower?

¿what problem do you want to solve?

by the way, ¿width >= height? ¿may rotate blocks?

what can you do with it if you sort all the blocks by height, and then again by width, and then in some way consume them to solve the problem? That is only a bit over NlgN run time... but as noted your problem statement is not complete yet.

Registered users can post here. Sign in or register to post.