The Skyline Problem

It's our first challenge. So to make a long story short let's start with the problem description.

"You are to design a program to assist an architect in drawing the skyline of a city given the locations of the buildings in the city. To make the problem tractable, all buildings are rectangular in shape and they share a common bottom. A building is specified by a triple (left and right coordinate and the height)...

In the diagram above buildings are shown on the left and the skyline is shown on the right..."

To sum up, you are given a list of the buildings and your task is to find the skyline (so that you can tell what is the highest point for every location in the city). What is more, the performance of your solution should be O(n log n).

In the original problem description the input/output representations are provided. But we decided to remove that hints just to show you how it gets complicated once you have to come up with your own. So if you have a similar problem during for example a job interview it might be worth talking about the details with your interviewer just to make sure if he has forgotten to tell you about some small details or did it on purpose. He might be also expecting you to ask that question before starting your intellectual battle. You never know...