Daily bit(e) of C++ | Skyline outline

Daily bit(e) of C++ #86, Common interview problem: Skyline outline

Today we will look at a common C++ interview problem: Skyline outline

Given information about buildings, where each building is represented by its left and right borders and height, produce the skyline outline represented by points that are the left starting points of each horizontal line.

Input is sorted by the left border; the output should be minimal and sorted by position.

For example, the input {{1,3,5}} (a single building starting at position 1 and ending at position 3 with height 5) should produce the output {{1,5},{3,0}}.

Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/jYWec5cPa.

Solution

There are several ways to approach this problem. I have chosen a basic solution, as this problem is great for demonstrating a straightforward divide-and-conquer approach.

Divide and conquer can be used under the following conditions:

• we can recursively divide the input into halves

• we can produce an output for a single element

• if we have two partial solutions, we can merge them in O(n) time

For our case, dividing the input is trivial, as we have a list of buildings; the same goes for the single-element solutions. The only non-trivial part is merging two partial solutions in O(n) time.

Click to open in Compiler Explorer.

---