Although there exists an O(n^{2}) solution, I will be describing the O(nlogn) solution here which uses recursion.

The basic idea is to think in terms of **skylines** instead of buildings. So a single building of the form: `[2,9,10]`

is actually a skyline of the form: `[ [2,9] , [10,0] ]`

. Now we just need to think of a way to merge two skylines, which will allow us to recursively merge all our skylines together!

**CONVERT TO SKYLINES**

To begin, let's convert the buildings to skyline form so we don't have to juggle two data structures:

```
skylines = []
for b in buildings: # b = [Li, Ri, Hi]
skylines.append([[b[0], b[2]],[b[1], 0]]) # [ [Li,Hi] , [Ri,0] ]
```

**MERGE SKYLINES**

It's easier to introduce a new function, `mergeSkylines(skylines)`

instead of dealing with the method we're given. This method takes a **list of skylines**, and returns a single **skyline**.

```
def mergeSkylines(skylines):
...
...
return skyline
```

**FIRST BASE CASE**

With usual recursion, we need a base case(s). In this case, we'll have two. The

first is having 1 skyline in our list. If that happens, we just return it.

```
if len(skylines) == 1: # A single skyline is 'already merged'
return skylines[0]
```

**SECOND BASE CASE**

The second base case is when we have exactly **two skylines**. Merging them will require a bit of work. The code may seem intimidating, but there's a simple idea behind it. First we need to notice that a skyline will have an ascending `x`

order:

```
skyline = [[5, 12], [12, 0], [15, 10], [20, 8], [24, 0]]
```

Let's say we want to merge these two skylines:

```
skyline_l = [[2, 10], [9, 0]]
skyline_r = [[3, 15], [7, 0]]
```

We need to keep track of each skyline's height independently. The highest of either skyline will always be the resulting height. If the building is in the back, we'll see it. If it's in the front, we'll see. So max height always wins. That's the first trick.

The second trick is to go through each point in `skyline_l`

and `skyline_r`

in order. And use that skyline's `x`

value along with the highest `y`

value from EITHER skyline.

```
yl = 0
yr = 0
x = 0
full_skyline = []
while len(l_skyline) > 0 or len(r_skyline) > 0:
xl = l_skyline[0]
xr = r_skyline[0]
if xl < xr:
p = l_skyline.pop(0)
x = p[0]
yl = p[1]
else:
p = r_skyline.pop(0)
x = p[0]
yr = p[1]
full_skyline.append([x,max(yl,yr)])
```

Ops, what if one skylines ends?? We can catch that, and just add all the points from the non-empty skyline to our merged list. So the fixed code will look like:

```
while len(l_skyline) > 0 or len(r_skyline) > 0:
if len(l_skyline) == 0:
full_skyline.extend(r_skyline)
break
if len(r_skyline) == 0:
full_skyline.extend(l_skyline)
break
xl = l_skyline[0]
xr = r_skyline[0]
if xl < xr:
p = l_skyline.pop(0)
x = p[0]
yl = p[1]
else:
p = r_skyline.pop(0)
x = p[0]
yr = p[1]
full_skyline.append([x,max(yl,yr)])
```

But wait, this might introduce successive points with the same height! We can fix that by going through our merged skyline and only keeping points that have a different height from the one before it:

```
fixed_full_skyline = [full_skyline[0]]
for p in full_skyline:
if p[1] != fixed_full_skyline[-1][1]:
fixed_full_skyline.append(p)
```

**MERGE STEP**

Ok that was a lot ... luckily the merge step is much simpler. Just merge the left and right halves of our skylines list. Then merge the resulting two skylines:

```
skyline_1 = mergeSkylines( skylines[:num/2] )
skyline_2 = mergeSkylines( skylines[num/2:] )
return mergeSkylines([ skyline_1, skyline_2 ])
```

Putting everything together, our solution will look like:

```
def getSkyline(buildings):
"""
:type buildings: List[List[int]]
:rtype: List[List[int]]
"""
# Convert single building into skyline
skylines = []
for b in buildings:
skylines.append([[b[0], b[2]],[b[1], 0]])
return mergeSkylines(skylines)
def mergeSkylines(skylines):
num = len(skylines)
if num == 1:
return skylines[0]
if num == 2:
l_skyline = skylines[0]
r_skyline = skylines[1]
yl = 0
yr = 0
x = 0
full_skyline = []
while len(l_skyline) > 0 or len(r_skyline) > 0:
if len(l_skyline) == 0:
full_skyline.extend(r_skyline)
break
if len(r_skyline) == 0:
full_skyline.extend(l_skyline)
break
xl = l_skyline[0]
xr = r_skyline[0]
if xl < xr:
p = l_skyline.pop(0)
x = p[0]
yl = p[1]
else:
p = r_skyline.pop(0)
x = p[0]
yr = p[1]
full_skyline.append([x,max(yl,yr)])
fixed_full_skyline = [full_skyline[0]]
for p in full_skyline:
if p[1] != fixed_full_skyline[-1][1]:
fixed_full_skyline.append(p)
return fixed_full_skyline
skyline_1 = mergeSkylines( skylines[:num/2] )
skyline_2 = mergeSkylines( skylines[num/2:] )
return mergeSkylines([ skyline_1, skyline_2 ])
```