Skyline Problem

Published: May 26, 2017

The skyline problem is another famous algorithm problem using bars, like Lagest Rectangle in a Histogram. Although the problem is described using bars, it is totally another problem compared to the largest rectangle. The skyline problem asks range maximum values.

While the largest rectangle has almost only one effective algorithm (using stack), this problem has a few effective ways to solve it.

For example:

The first solution by heap sort is the most popular, simplest way. So, the solutions are here and there with a slight variation. The second, divide and conquer (merge sort) is interesting solution. Not so popular, but still a few are using this technique. The third by the segement tree is not so popular, but shows very unique two-step solution. In case of the segment tree, the tree should be created first. Then making queries of intervals gives the result.

Problem Description

The coordinates of each building will be given by [left, right, height]. The input is an array of three element arrays. For example,

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

This input creates buildings below:


   .
18 .                                     +-----+
   .                                     |     |
   .                                     |     |
15 .                                     |     |
   .                                     |     |
   .     +-----------+                   |     | +-----------+
   .     |           |                   |     | |           |
   . +---|----+      |                   |     | |           |
10 . |   |    |      |                   |     | |           |
   . |   |    |      |                   |     | |           |
   . |   |    |      |                   |     | |           |
   . |   |    |      |     +-------+     |     | |           |
   . | +-|-------+   |     |       |     |     | |           |
 5 . | | |    |  |   |     |       |     |     | |           |
   . | | |    |  |   |     |       |     |     | | +-------+ |
   . | | |    |  |   |     |   +---------|-----|-|-|-+     | |
   . | | |    |  |   |     |   |   |     |     | | | |     | |
   . | | |    |  |   |     |   |   |     |     | | | |     | |
 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
   0         5         10        15        20        25        30

From this input, the problem requires to find [position, height] pairs to draw outer shape. In the picture below, positions of @ should be returned. Since, lines only go left, up or down, @s are enough to draw the outer shape (skyline).

[[1, 11], [3, 13], [9, 0], [12, 7], [16, 3], [19, 18], [22, 3], [23, 13], [29, 0]]

   .
18 .                                     @-----+
   .                                     |     |
   .                                     |     |
15 .                                     |     |
   .                                     |     |
   .     @-----------+                   |     | @-----------+
   .     |           |                   |     | |           |
   . @---|           |                   |     | |           |
10 . |               |                   |     | |           |
   . |               |                   |     | |           |
   . |               |                   |     | |           |
   . |               |     @-------+     |     | |           |
   . |               |     |       |     |     | |           |
 5 . |               |     |       |     |     | |           |
   . |               |     |       |     |     | |           |
   . |               |     |       @-----|     @-|           |
   . |               |     |       |     |     | |           |
   . |               |     |       |     |     | |           |
 0 . . . . . . . . . @ . . . . . . . . . . . . . . . . . . . @ . .
   0         5         10        15        20        25        30

The idea

As far as I compared three well-cited solutions, I decided to choose the first, heap sort solution. It is simple and easy to understand. However, I ended up in a slight variation of the typical way.

The key ideas is re-queuing the lower height buildings as possible surviors. All buildings are sorted by the left position (starting position). If multiple buildings have the same left value, those will be sorted by their height. Before the re-queuing lower height buildings, those left position will be adjusted to the end of a current maximum height building. This way, when the higher building ends, the lower previously started buildings show up again as possible candidates.

Not like typical heap sort solutions, my solution uses one PriorityQueue only. Although there’s not a big difference in terms of big-O notation, it is slightly space effective. Downside is time complexity depends on how buildings are shaped. This solution was accepted by LeetCode testing (14 ms), it won’t so bad even though building locations are complicated.

Java code

Below is the Java code explaied above.

The result is:

[[1, 11], [3, 13], [9, 0], [12, 7], [16, 3], [19, 18], [22, 3], [23, 13], [29, 0]]
[[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]

Thoughts

If I neglect real height differences of the skyline and delete vertical bars, it turns to below:


   .                                     @-----
   .     @-----------                            @-----------
   . @---                                                     
   .                       @-------                          
   .                               @-----      @-             
   . . . . . . . . . @-----. . . . . . . . . . . . . . . . . @ . .
   0         5         10        15        20        25        30

This has been seen somewhere else. It is quite similar to a weighted scheduling problem. Most weighted scheduling doesn’t require lower priority jobs to come back. However, if it does, the solution will be almost equivalant to the skyline problem.

Resources

Latest Posts

Setting Up GCP Instance for Deep Learning

This post is going to be very different from what I write here. The content is a memo how I create a GCP (Google Cloud Platform) instance for Deep Learning. While I study algorithm stuff, I also have been studying Deep Learning. In my early days, I tried to train my Deep Learning model only on a laptop. My laptop is 2012 model MacBook Pro, so I would say it is reasonably fast. However, when it comes to Deep Learning, the training was quite painful on the such machine. Often, I ran the training over night to get a disappointed result. Still, I didn’t use any of pricey cloud environment since it was my personal study unrelated to my day job. I wanted to save money.

Complete Binary Tree

Problems which ask a binary tree traverse, add/delete nodes, etc. are popular in algorithm questions. The binary trees are often just a binary tree or binary search tree. Sometimes, the problem pinpoints a particular type of a binary tree, for example, a balanced binary tree or complete binary tree.

Catalan number

What is Catalan number ? The Catalan number belongs to the domain of combinatorial mathematics. It is a sequence of natural numbers such that: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, ... The sequence appears in counting problems. Wikipedia has the details about the sequence: Catalan Number.