Finally got this wonderful logic: store a zoomed in version of each building. Each building is stored in a 5 times zoomed in size. So, if a building is (1 11 5) it will be stored as (5 11 25) which means start at 5, end at 25 with height as 11.
Tracing the skyline using the above is quite simple :-)
Go until a non-zero height building is found.
Compare height at x and x + 1:
    If we have a difference, print x, height(x)
    else increment x
Took me a couple of months, constant thinking and a whiteboard to get here.
Now, for some more tests before submit.