• 26.2%

https://leetcode.com/problems/the-skyline-problem/?tab=Description

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], … ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

• The number of buildings in any input list is guaranteed to be in the range [0, 10000].
• The input list is already sorted in ascending order by the left x position Li.
• The output list must be sorted by the x position.
• There must be no consecutive horizontal lines of equal height in the output skyline. For instance, […[2 3], [4 5], [7 5], [11 5], [12 7]…] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: […[2 3], [4 5], [12 7], …]

https://discuss.leetcode.com/topic/39416/guaranteed-really-detailed-and-good-perfect-explanation-of-the-skyline-problem

https://briangordon.github.io/2014/08/the-skyline-problem.html

https://discuss.leetcode.com/topic/14939/my-c-code-using-one-priority-queue-812-ms

My C++ code using one priority queue (812 ms)

The idea is to do line sweep and just process the buildings only at the start and end points. The key is to use a priority queue to save all the buildings that are still “alive”. The queue is sorted by its height and end time (the larger height first and if equal height, the one with a bigger end time first). For each iteration, we first find the current process time, which is either the next new building start time or the end time of the top entry of the live queue. If the new building start time is larger than the top one end time, then process the one in the queue first (pop them until it is empty or find the first one that ends after the new building); otherswise, if the new building starts before the top one ends, then process the new building (just put them in the queue). After processing, output it to the resulting vector if the height changes. Complexity is the worst case O(NlogN)

Not sure why my algorithm is so slow considering others’ Python solution can achieve 160ms, any commments?

https://discuss.leetcode.com/topic/14939/my-c-code-using-one-priority-queue-812-ms/2

Very nice idea, keeping smaller buildings alive under larger ones even though they ended already.

You have a few unnecessary things, though. If I’m not mistaken, mycompare just does the default ordering, vector is the default container for priority_queue, the if(len>0) doesn’t help, and you don’t need a private section. I think removing that stuff would make your solution even better than it already is.

About Python being faster: Yeah that’s right, Python is faster now. Deal with it :-P. More seriously, here’s the probable explanation.

https://discuss.leetcode.com/topic/16511/share-my-divide-and-conquer-java-solution-464-ms

Share my divide and conquer java solution, 464 ms

Detailed explanation: http://www.geeksforgeeks.org/divide-and-conquer-set-7-the-skyline-problem/

https://discuss.leetcode.com/topic/25794/17-line-o-n-log-n-time-o-n-space-c-accepted-easy-solution-w-explanations

17-Line O(n log n)-time O(n)-space C++ Accepted Easy Solution w/ Explanations

General idea:

Step 1:

Use a multimap to sort all boundary points. For a start point of an interval, let the height be positive; otherwise, let the height be negative. Time complexity: O(n log n)

Step 2:

Use a multiset (rather than a heap/priority_queue) to maintain the current set of heights to be considered. If a new start point is met, insert the height into the set, otherwise, delete the height. The current max height is the back() element of the multiset. For each point, the time complexity is O(log n). The overall time complexity is O(n log n).

Step 3:

Delete the points with equal heights. Time: O(n)

Time Complexity: O(n log n)

Space Complexity: O(n)

C++

In fact, the last two steps can be merged together:

Yet another solution (C++):

https://discuss.leetcode.com/topic/14987/108-ms-17-lines-body-explained

108 ms, 17 lines body, explained

This is a Python version of my modification of dong.wang.1694’s brilliant C++ solution. It sweeps from left to right. But it doesn’t only keep heights of “alive buildings” in the priority queue and it doesn’t remove them as soon as their building is left behind. Instead, (height, right) pairs are kept in the priority queue and they stay in there as long as there’s a larger height in there, not just until their building is left behind.

In each loop, we first check what has the smaller x-coordinate: adding the next building from the input, or removing the next building from the queue. In case of a tie, adding buildings wins, as that guarantees correctness (think about it :-). We then either add all input buildings starting at that x-coordinate or we remove all queued buildings ending at that x-coordinate or earlier (remember we keep buildings in the queue as long as they’re “under the roof” of a larger actually alive building). And then, if the current maximum height in the queue differs from the last in the skyline, we add it to the skyline.

https://discuss.leetcode.com/topic/35817/recommend-for-beginners-clean-c-implementation-with-detailed-explanation

[recommend for beginners]clean C++ implementation with detailed explanation

https://discuss.leetcode.com/topic/26420/14-line-python-code-straightforward-easy-to-understand

14 line python code, straightforward & easy to understand

https://discuss.leetcode.com/topic/34119/10-line-python-solution-104-ms

10-line Python solution, 104 ms

Use an infinite vertical line x to scan from left to right. If max height changes, record [x, height] in res. Online judge is using Python 2.7.9 and there’s no max heap’s push and pop method, so we can use a min heap hp storing -H as “max heap”. Thanks to this discussion, set comprehension is faster and shorter than list(set((R, 0, None) for L, R, H in buildings)).

https://discuss.leetcode.com/topic/22482/short-java-solution

Short Java solution

https://discuss.leetcode.com/topic/28482/once-for-all-explanation-with-clean-java-code-o-n-2-time-o-n-space

Once for all, explanation with clean Java code(O(n^2)time, O(n) space)

Though I came up with a solution using PriorityQueue and BST, this problems still confuses me. To make it more clear, I went through it several times and investigated several good solutions on this forum.

Here is my explanation which tries to make understanding this easier and may help you write a bug-free solution quickly.

When visiting all start points and end points in order:

Observations:

Tus we have:

Obviously, to implement the idea that ‘current height takes effect’ and ‘find out whether current height is shadowed by other buildings’, we need a mechanism to store current taking effect heights, meanwhile, figure out which one is the maximum, delete it if needed efficiently, which hints us to use a priority queue or BST.

Thus, our algorithm could be summarised in following pseudo code:

To implement this algorithm, here are some concrete examples:

In my implementation, I use a PriorityQueue to store end point values when visiting a start point, and store the [height, end point value] into a TreeMap. Thus:

``````1. when moving to next start point value, I can compare the next start point value with elements in PriorityQueue, thus achieving visiting all start points and end points in order(exploits the fact that start points are already sorted);
2. Meantime, I can get current max height from TreeMap in O(logn);
3. However, to delete a height when visiting a end point, I have to use 'map.values.remove()' which is a method defined in Collection interface and tends to be slower(O(n) is this case, plz correct me if I'm wrong);
``````

My code can be found at https://leetcode.com/discuss/62617/short-and-clean-java-solution-heap-and-treemap

Following is wujin’s implementation(plz refer to https://leetcode.com/discuss/54201/short-java-solution). This one is quite straightforward, clean and clever.
Firstly, please notice what we need to achieve:

To achieve this, his implementation:

Thus,

His code is as follows(clear and concise) as reference with my comment(again, https://leetcode.com/discuss/54201/short-java-solution):

Hopefully now, you can write a good solution in a blink with good understanding…