DIY: The Skyline Problem

Solve the interview question "The Skyline Problem" in this lesson.

Problem statement

Given a buildings list, you have to draw the skyline of the outer contour of the city. The citys’ skyline is formed by the silhouette of all of its buildings. Each building in this buildingslist consists of the following information:

  • lefti: The x-coordinate of the left edge of the building.
  • righti: The x-coordinate of the right edge of the building.
  • heighti: The height of the building.

The skyline should consist of a list of coordinates, sorted according to their x-coordinates. This list should be in the form of [[x1,y1],[x2 ,y2],…[xn ,yn]]. Each coordinate in the skyline is the left coordinate of a horizontal segment, except the last point, whose y-coordinate is always be 0. We will use this last point to mark the end, where the rightmost building ends. In the skyline, no two consecutive coordinates should have the same y-coordinate. For example, [[2,3],[4,3],[7,3]] is not acceptable. They should be merged into one coordinate, that is [2,3] to be accepted.

Note: You may assume that all the buildings are perfect rectangles and are grounded on height 0.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.