Perhaps I’ve misunderstood the problem, but the second solution shown here doesn’t seem to be correct: it always adds a trailing 0-height entry to the skyline, yet there could be an existing building touching or overlapping the newly added building, whose height is then lost.<p>For example, the code given appears to make<p><pre><code> skyline [(1, 2, 3), (2, 1, 4)]
</code></pre>
evaluate to<p><pre><code> [(1,2),(3,0),(4,0)]
</code></pre>
when if I’ve understood correctly it should be<p><pre><code> [(1,2),(3,1),(4,0)]</code></pre>
I was given this exact problem at a Google interview. In fact it was virtually the only high level, real code programming exercise I was asked to do in many hours of interviews.
For those of us not particularly skilled at Haskell, could you add some comments on the actual code, or at least explain some of the lines? I get the English part of the algorithm, but I don't think I'm up to speed on some of the syntax being used in your solutions.