The Skyline problem

Problem

Given N buildings in a x-axis, each building is a rectangle and can be represented by a triple (start, end, height), where start is the start position on x-axis, end is the end position on x-axis and height is the height of the building. Buildings may overlap if you see them from far away, find the outline of them。

An outline can be represented by a triple, (start, end, height), where start is the start position on x-axis of the outline, end is the end position on x-axis and height is the height of the outline.

Note: Please merge the adjacent outlines if they have the same height and make sure different outlines cant overlap on x-axis.

Example

Given 3 buildings:

[
  [1, 3, 3],
  [2, 4, 4],
  [5, 6, 1]
]

The outlines are:

[
  [1, 2, 3],
  [2, 4, 4],
  [5, 6, 1]
]

Solution

From the input, create tuples (x, height, isStart), so each building will create 2 tuples, one for start point and one for end point. Sort the tuples by x, then for each tuple:

• if start:
  • if height higher than previous height, a new segment! Add to the result and push the height to the heap
  • otherwise just push the height to the heap.
• else end:
  • if height lower than the highest height from the heap, just delete it(or mark it as deleted)
  • else a new segment! Add to the result and pop from the heap.

Note: during sorting, for the same x, end point should be prior to the start point to prevent multiple segments at the same height.