Figuring Algo for assignment
Hey all, I just received my next assigment frommy data structures and discrete math class; I have a hunch on how to do it but I can't think of the base case...anyways here is roughly what I have to do:
Title: Skyline problem
There is a city with no hills and has a set of rectangular buildings. Suppose you are viewing the city from water. Leftmost position of city is used as reference point ( horiz position 0 ). This, a building can be speified by (l, h, w), where l gives the left boundary, h the height of the buildingsm and w its width.
the program will take as input a set of n buildings, in no particular order. The program now has to extract the outline formed by the buildings. This skyline will be formed by a sequence of horizontal segments starting at position 0. It will be represented by a equence of pairs (h, w) where h is the height abd w the width.
there are some restirictions for the design: must use divide and conquer algorithm and must be linear time operation.
So basically if the input from a file is:
(13, 3 4), (3,6,6,), (1,2,9), (14, 2,5), (18,4,2)
the corresponding output will be:
(0,1), (2,2), (6,6), (2,1),(0,3),(3,4),(2,1),(4,2)
I hope you guys understand what the qestion is asking for, i tried to "draw" a picture of what it supposed to be
since it is a D&C algo, I was thinking of using a similar algo to merge sort, where I would break the n buildings into two groups of roughly equal size, and then recursively find the skyline of each group.
| | | ______
0 a b c d e
____ __________ ____ ______ ______
0 a b c d e
where all the red pieces would correspond to the output sequence of pairs (hi, wi)
The problem is that I'm not sure how it will work for a base case, ie. if the is only one building.
any comments? suggestions on how to go about it?