Haskell SkylineHadi Moshayedi
Recently I started learning Haskell by studying the Intro to FP Programming course on Edx. Since then, I try to model different problems using Haskell.
One of these problems is the Skyline problem, which goes like this:
You are given a set of rectangular buildings in a city, and you should return the skyline view of the city. Input is a sequence of tuples , each describing a building. The output is a sequence of pairs meaning that the height of skyline changed to at the given x coordinate.
For example, for the input:
The output should be:
Below diagrams show the input buildings and the expected skyline side by side:
Solving the problem
You can find an extended analysis of this problem at Brian Gordon’s blog , which explains several solutions of and complexity to this problem.
Since sorting of integers can easily be reduce to this problem in linear time,
this problem isn’t solvable faster than time. (See comments)
In this post I’m not concerned with the time complexity at all, but mostly with the simplicity of the solution.
It’s also okay if a solution if contains a false height change, i.e. if we have two consecutive items in the output that contain the same height. After all, we are only concerned with how the skyline will look, and having a false change doesn’t change the shape of skyline.
Solution 1. Calculate height of skyline at all endpoints
We’re only interested at changes to the height of skyline, and height can only change where a building starts or ends. The height at a point can be calculated by finding the max height of buildings overlapping that point.
This leads us to the following solution:
This solution has time complexity of and produces some false changes, but it is very simple and easy to understand.
(We can easily remove the false changes by passing the result through another function, but this is good enough for our purpose and our goal is to keep things simple).
Solution 2. Iteratively add buildings
One might think we can iteratively add buildings and update the shape of skyline. Since a building can be taller or shorter than the previously added buildings, we may need to handle several cases to make this work correctly.
But if we sort the buildings by height before adding them, we can make the update much simpler. If we know the height of skyline is shorter than current building, then all we need to do is to remove the previous points between the boundries of the current building (since they won’t be visible anymore), and then add the two points of building.
This leads us to the following solution:
Update. Initial version of this code, which wrongly added
add_building was incorrect, for the reason described by Chris_Newton
I think this also looks very simple, although not as simple as the previous solution, with the advantage that it won’t generate false height changes as much as previous solution.
The time complexity of this solution is , but if we had used some sort
of sorted search tree with operations instead of using lists,
this could easily be improved to . After all what we do here is one
simple iteration with
foldl, and then adding each point exactly once, and
removing each end point at most once.
height xs y can also be implemented in if xs is
some kind of sorted search tree.
Solution 3. Divide and Conquer
Since this is functional programming and solutions usually tend to be solved using recursion, we could use a solution similar to merge sort. That is, solve the shape of skyline for each half of the buildings, and then merge the shapes.
The solution will look like:
merge function doesn’t seem very simple, so I wouldn’t use this solution
if I could use a simpler solution.
Similar to merge sort, the time complexity of this solution is .
There are other solutions to this problem too, but I think these three solutions are good representative of the solution space. I love problems which can be solved in several totally different ways, and I found it beautiful that some of the solutions are strikingly simple and easy to understand.