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??
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.