Give a list of tuples – where each tuple has 3 value – (x1, x2, h1) – each tuple represents a rectangular block of a building in the city skyline.
x1 – Start Coordinate of a Block on X Axis
x2 – End Coordinate of a Block on X Axis
h1 – Height of the block
Once a list of such tuples is given he problem is to find out the general skyline of the City int he 2D plane – where 1 building’s coordinates could be overlapping with another building and changing the skyline from a 2D perspective
For Example if we have a set of tuples as below
The general skyline algorithm should return
(1,4,10), (4,6,12), (6,9,15), (9,15,12)
I use a recursive Divide and Conquer Algorithm where I break up the original list into a list of smaller tuples.
When there is only 1 or 2 tuple in a list – we call the merge() routine to merge 2 tuples.
The results are printed as a set of blocks using matplotlib graphing library
python SkyLineNew.py 1 4 10 4 6 12 6 9 15 9 15 12
// where you have a set of 3 numbers – which represents a tuple and
// have any number of such tuples
// the program exits if any number is a -ve number and if the
// number of entries is not a multiple of 3
The code finally generates a graph of the Skyline using matplotlib python library – something like the one below