Silhouette of some buildings in a city - Need help coding this algorithm, please!

[1_2_Soar]

Imagine the skyline of a city:- you are given (in integers)
(1) the x-coordinate,
(2) the height,
(3) and the width
measurements for a number of the buildings.

You are required to give the silhouette of those buildings in that city.

By the way, someone else has a descriptive posting in this problem domain (in the link provided below), in an entirely unrelated discussion.

I wish that, they had posted the solution as well. :)

http://www.facweb.iitkgp.ernet.in/~niloy/studentscorner/my%20microsoft%20experiences.pdf

[pm_kirkham]

For small integers, just draw them on a bitmap and walk along the boundary.

Other than that, a tree or skip list where inserting a rectangle can split a node in two so that given an initial SkyLine(height, min_x, max_x) of (0, min, max) then adding (8, 10, 20) you get [(0,min,10),(8,10,20),(0,20,max)] as leaf elements.

[ProgramThis]

This is a fairly common hw assignment. If you assume the obvious (that you have all of the buildings in either a sorted array or a tree / list with the first X value being the priority), then you simply have to walk through all of the elements.

Sounds easy? Well, there is one more thing that you have to account for: When ever you reach increase in height, you need to keep track of the building(s) that you are moving up from IFF those buildings, from the current position, are wider than the width of the one you are currently working on (the new building with hight X > Previous). Once you reach the far end of the current building you either need to drop down to the value that you saved, OR you need to check if any other buildings with height X > Previous have come into the picture.

Read this page (http://discuss.joelonsoftware.com/default.asp?interview.11.600813.7) which has a pseudo algorithm for solving the problem.