- 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://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?

1 | class Solution { |

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/

1 | public class Solution { |

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++

1 | class Solution { |

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

Yet another solution (C++):

1 | class Solution { |

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.

1 | from heapq import * |

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

1 | class Solution { |

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

14 line python code, straightforward & easy to understand

1 | class Solution(object): |

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)).

1 | def getSkyline(self, buildings): |

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

Short Java solution

1 | public List<int[]> getSkyline(int[][] buildings) { |

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:

1 | If a position is shadowed by other buildings |

Tus we have:

1 | 1. when you reach a start point, the height of current building immediately |

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:

1 | for position in sorted(all start points and all end points) |

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:

1 | 1. visit all start points and all end points in order; |

To achieve this, his implementation:

1 | 1. use a int[][] to collect all [start point, - height] and [end point, height] |

Thus,

1 | 1. we can visit all points in order; |

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

1 | public List<int[]> getSkyline(int[][] buildings) { |

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