# 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.