Help me figure this problem out please...

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 narrow one. And you may not put a shorter block on top of a taller one (no rotation allowed). You are trying to get as high as possible. The number of blocks goes up to 100000 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 maybe get somewhere, at the moment I am not figuring out anything :/ :D!

>Get the highest possible tower

>No rotation

>Up to 100,000 different blocks

>Only a few seconds execution

>Could there be some sort of pattern for every case??

Thank you!
Last edited on
This is a fun little exercise. I'll just give you a few hints.

1. You need to first sort the list of blocks.
2. You need to construct a directed acyclic graph using the sorted list.
3. You need to walk the DAG looking for the longest chain of blocks.

Interestingly enough, I had to do something similar to this a few weeks ago to construct a Bitcoin blockchain.
>This is a fun little exercise. I'll just give you a few hints.

Thanks for quick reply! I'll take a deep look at it :D
Registered users can post here. Sign in or register to post.