## Skyline Puzzle

### September 5, 2014

There are several ways to solve this problem. Our solution works in two passes: the first pass collects the maximum height at each x-coordinate, and the second pass outputs a portion of the skyline each time the height changes. Here’s the first pass:

`(define (heights buildings)`

(let* ((len (apply max (map caddr buildings)))

(hites (make-vector (+ len 1) 0)))

(do ((buildings buildings (cdr buildings)))

((null? buildings) (vector->list hites))

(let ((building (car buildings)))

(do ((x (car building) (+ x 1))) ((= x (caddr building)))

(vector-set! hites x

(max (vector-ref hites x) (cadr building))))))))

We cheat by making a pre-pass before the first pass to compute the width of the skyline, which is stored in the `len`

variable. The outer `do`

iterates over the input buildings and the inner `do`

iterates over the x-coordinates from each building’s left edge to its right edge. The second pass runs through the list of heights, printing output each time the height changes:

`(define (skyline buildings)`

(let loop ((x 0) (prev 0) (hites (heights buildings)) (skys (list)))

(cond ((null? hites) (reverse skys))

((= (car hites) prev) (loop (+ x 1) prev (cdr hites) skys))

(else (loop (+ x 1) (car hites) (cdr hites) (cons (car hites) (cons x skys)))))))

Here’s the output from the example problem:

`> (skyline '((1 11 5) (2 6 7) (3 13 9) (12 7 16)`

(14 3 25) (19 18 22) (23 13 29) (24 4 28)))

(1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0)

You can run the program at http://programmingpraxis.codepad.org/0YYexYt9.

In perl

Java 8 solution

public static List skyLinePuzzle(List buildings)

{

int start = buildings.stream().map(b -> b.start).min(Integer::compareTo).orElse(0);

int end = buildings.stream().map(b -> b.end).max(Integer::compareTo).orElse(start);

List result = newArrayList();

int lastHeight = -1;

for (int i = start; i b.start <= index && index

b.height).max(Integer::compareTo).orElse(0);if (height != lastHeight)

{

result.add(index);

result.add(height);

lastHeight = height;

}

}

return result;

}

Java 8 with Formatter from http://java2html.blogspot.de/

Haskell. Make a list of start/end positions and heights. Sort it, then scan to find maximum height at each point, finally filter out redundant entries and flatten list:

Slightly improved version: Haskell insert/insertBy keeps list ordered, so can just use head to get maximum height (a serious implementation might use a heap-based priority queue here). Complexity is m n log n, for n buildings, maximum overlapping buildings m.

In Python. This solution is way more complicated than it should be, but this should also work for real x, y coordinates and can handle large cities as well. First sort all buidling on height (descending) and then build a BST. If a building is overlapping with a higher building, cut off the overlapping part and feed it down the tree. The result is a tree with non-verlapping intervals, that are visible in the skyline.

On Stack Overflow you can find much shorter solutions.

My lengthy Scheme solution:

A simple solution in Python 3 –

p = [(1,11,5),(2,6,7),(3,13,9),(12,7,16),(14,3,25),(19,18,22),(23,13,29),(24,4,28)]

def find_skyline(blds):

# ensure the building coordinates are x – axis sorted

blds.sort()

# transform the coodinates to left & right edges (right -ve height)

points = []

for p in blds:

points.append((p[0], p[1]))

points.append((p[2], -p[1]))

points.sort()

#print(points) # print for debuggung

top = 0 # top / ceiling for traversal

drp = 0 # height stack for right edge

skln = [] # skyline points

for p in points:

if p[1] > 0:

# left edges

if p[1] > top:

top = p[1]

skln.append((p[0], top))

drp += p[1]

else:

# right edges

drp += p[1]

if abs(p[1]) > drp:

top = drp

skln.append((p[0], top))

return skln

print(find_skyline (p))

#(1 11) (3 13) (9 0) (12 7) (16 3) (19 18) (22 3) (23 13) (29 0)

Simple Python 3 solution –

A simple Clojure solution; this is not the most efficient, as it makes multiple passes over the list of buildings to compute the height at each point.