218. The Skyline Problem

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

image

image

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?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
vector<pair<int, int>> res;
int cur=0, cur_X, cur_H =-1, len = buildings.size();
priority_queue< pair<int, int>> liveBlg; // first: height, second, end time
while(cur<len || !liveBlg.empty())
{ // if either some new building is not processed or live building queue is not empty
cur_X = liveBlg.empty()? buildings[cur][0]:liveBlg.top().second; // next timing point to process

if(cur>=len || buildings[cur][0] > cur_X)
{ //first check if the current tallest building will end before the next timing point
// pop up the processed buildings, i.e. those have height no larger than cur_H and end before the top one
while(!liveBlg.empty() && ( liveBlg.top().second <= cur_X) ) liveBlg.pop();
}
else
{ // if the next new building starts before the top one ends, process the new building in the vector
cur_X = buildings[cur][0];
while(cur<len && buildings[cur][0]== cur_X) // go through all the new buildings that starts at the same point
{ // just push them in the queue
liveBlg.push(make_pair(buildings[cur][2], buildings[cur][1]));
cur++;
}
}
cur_H = liveBlg.empty()?0:liveBlg.top().first; // outut the top one
if(res.empty() || (res.back().second != cur_H) ) res.push_back(make_pair(cur_X, cur_H));
}
return res;
}
};

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class Solution {
public List<int[]> getSkyline(int[][] buildings) {
if (buildings.length == 0)
return new LinkedList<int[]>();
return recurSkyline(buildings, 0, buildings.length - 1);
}

private LinkedList<int[]> recurSkyline(int[][] buildings, int p, int q) {
if (p < q) {
int mid = p + (q - p) / 2;
return merge(recurSkyline(buildings, p, mid),
recurSkyline(buildings, mid + 1, q));
} else {
LinkedList<int[]> rs = new LinkedList<int[]>();
rs.add(new int[] { buildings[p][0], buildings[p][2] });
rs.add(new int[] { buildings[p][1], 0 });
return rs;
}
}

private LinkedList<int[]> merge(LinkedList<int[]> l1, LinkedList<int[]> l2) {
LinkedList<int[]> rs = new LinkedList<int[]>();
int h1 = 0, h2 = 0;
while (l1.size() > 0 && l2.size() > 0) {
int x = 0, h = 0;
if (l1.getFirst()[0] < l2.getFirst()[0]) {
x = l1.getFirst()[0];
h1 = l1.getFirst()[1];
h = Math.max(h1, h2);
l1.removeFirst();
} else if (l1.getFirst()[0] > l2.getFirst()[0]) {
x = l2.getFirst()[0];
h2 = l2.getFirst()[1];
h = Math.max(h1, h2);
l2.removeFirst();
} else {
x = l1.getFirst()[0];
h1 = l1.getFirst()[1];
h2 = l2.getFirst()[1];
h = Math.max(h1, h2);
l1.removeFirst();
l2.removeFirst();
}
if (rs.size() == 0 || h != rs.getLast()[1]) {
rs.add(new int[] { x, h });
}
}
rs.addAll(l1);
rs.addAll(l2);
return rs;
}
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {

// Step 1:
multimap<int, int> coords;
for (const vector<int> & building : buildings) {
coords.emplace(building[0], building[2]);
coords.emplace(building[1], -building[2]);
}

// Step 2:
multiset<int> heights = { 0 };
map<int, int> corners;
for (const pair<int, int> & p : coords) {
if (p.second > 0) {
heights.insert(p.second);
}
else {
heights.erase(heights.find(-p.second));
}
int cur_y = *heights.rbegin();
corners[p.first] = cur_y;
}

// Step 3:
function<bool(pair<int, int> l, pair<int, int> r)> eq2nd = [](pair<int, int> l, pair<int, int> r){ return l.second == r.second; };
vector<pair<int, int>> results;
unique_copy(corners.begin(), corners.end(), back_insert_iterator<vector<pair<int, int>>>(results), eq2nd);
return results;
}
};

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

Yet another solution (C++):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
multimap<int, int> coords;
for (const vector<int> & building : buildings) {
coords.emplace(building[0], building[2]);
coords.emplace(building[1], -building[2]);
}

multiset<int> heights = { 0 };
vector<pair<int, int>> corners;
int x = -1;
int y = 0;
for (const pair<int, int> & p : coords) {
if ((x >= 0) && (p.first != x) && (corners.empty() || (corners.rbegin()->second != y))) {
corners.emplace_back(x, y);
}

if (p.second >= 0) {
heights.insert(p.second);
}
else {
heights.erase(heights.find(-p.second));
}

x = p.first;
y = *heights.rbegin();
}

if (!corners.empty()) {
corners.emplace_back(x, 0);
}

return corners;
}
};

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from heapq import *

class Solution:
def getSkyline(self, LRH):
skyline = []
i, n = 0, len(LRH)
liveHR = []
while i < n or liveHR:
if not liveHR or i < n and LRH[i][0] <= -liveHR[0][1]:
x = LRH[i][0]
while i < n and LRH[i][0] == x:
heappush(liveHR, (-LRH[i][2], -LRH[i][1]))
i += 1
else:
x = -liveHR[0][1]
while liveHR and -liveHR[0][1] <= x:
heappop(liveHR)
height = len(liveHR) and -liveHR[0][0]
if not skyline or height != skyline[-1][1]:
skyline += [x, height],
return 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
vector<pair<int, int>> edges;
int left, right, height;
for(int i=0; i<buildings.size(); i++){
left=buildings[i][0];
right=buildings[i][1];
height=buildings[i][2];
/*** make sure : for the same left point we use the bigger height ***/
edges.push_back(make_pair(left, -height));
edges.push_back(make_pair(right, height));
}
sort(edges.begin(), edges.end());
vector<pair<int, int>> result;
/*** use the multiset to store the max height util current pos ***/
multiset<int> m;
/*** left most height ***/
m.insert(0);
int pre=0, cur=0;
for(int i=0; i<edges.size(); i++){
pair<int, int> e=edges[i];
if(e.second < 0) m.insert(-e.second);
else m.erase(m.find(e.second));
cur=*(m.rbegin());
if(cur!=pre){
result.push_back(make_pair(e.first, cur));
pre=cur;
}
}
return result;
}
};

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

14 line python code, straightforward & easy to understand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution(object):
def getSkyline(self, buildings):
"""
:type buildings: List[List[int]]
:rtype: List[List[int]]
"""
def addsky(pos, hei):
if sky[-1][1] != hei:
sky.append([pos, hei])

sky = [[-1,0]]

# possible corner positions
position = set([b[0] for b in buildings] + [b[1] for b in buildings])

# live buildings
live = []

i = 0

for t in sorted(position):

# add the new buildings whose left side is lefter than position t
while i < len(buildings) and buildings[i][0] <= t:
heappush(live, (-buildings[i][2], buildings[i][1]))
i += 1

# remove the past buildings whose right side is lefter than position t
while live and live[0][1] <= t:
heappop(live)

# pick the highest existing building at this moment
h = -live[0][0] if live else 0
addsky(t, h)

return sky[1:]

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
2
3
4
5
6
7
8
9
10
11
def getSkyline(self, buildings):
events = sorted([(L, -H, R) for L, R, H in buildings] + list({(R, 0, None) for _, R, _ in buildings}))
res, hp = [[0, 0]], [(0, float("inf"))]
for x, negH, R in events:
while x >= hp[0][1]:
heapq.heappop(hp)
if negH:
heapq.heappush(hp, (negH, R))
if res[-1][1] + hp[0][0]:
res += [x, -hp[0][0]],
return res[1:]

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

Short Java solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> result = new ArrayList<>();
List<int[]> height = new ArrayList<>();
for(int[] b:buildings) {
height.add(new int[]{b[0], -b[2]});
height.add(new int[]{b[1], b[2]});
}
Collections.sort(height, (a, b) -> {
if(a[0] != b[0])
return a[0] - b[0];
return a[1] - b[1];
});
Queue<Integer> pq = new PriorityQueue<>((a, b) -> (b - a));
pq.offer(0);
int prev = 0;
for(int[] h:height) {
if(h[1] < 0) {
pq.offer(-h[1]);
} else {
pq.remove(h[1]);
}
int cur = pq.peek();
if(prev != cur) {
result.add(new int[]{h[0], cur});
prev = cur;
}
}
return result;
}

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:

1
2
3
4
5
6
7
8
If a position is shadowed by other buildings

1. height of that building is larger than the building to which current
position belong;
2. the start point of that building must be smaller(or equal to) than this
position;
3. the end point of that building must be larger(or equal to) than this
position;

Tus we have:

1
2
3
4
5
6
7
1. when you reach a start point, the height of current building immediately
takes effect which means it could possibly affect the contour or shadow
others when mixed with other following buildings;
2. when you reach a end point, the height of current building will stop its
influences;
3. our target exists at the position where height change happens and there
is nothing above it shadowing it;

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
2
3
4
5
6
7
8
for position in sorted(all start points and all end points)
if this position is a start point
add its height
else if this position is a end point
delete its height
compare current max height with previous max height, if different, add
current position together with this new max height to our result, at the
same time, update previous max height to current max height;

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
2
3
4
1. visit all start points and all end points in order;
2. when visiting a point, we need to know whether it is a start point or a
end point, based on which we can add a height or delete a height from
our data structure;

To achieve this, his implementation:

1
2
3
4
1. use a int[][] to collect all [start point, - height] and [end point, height]
for every building;
2. sort it, firstly based on the first value, then use the second to break
ties;

Thus,

1
2
3
4
1. we can visit all points in order;
2. when points have the same value, higher height will shadow the lower one;
3. we know whether current point is a start point or a end point based on the
sign of its height;

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> result = new ArrayList<>();
List<int[]> height = new ArrayList<>();
for(int[] b:buildings) {
// start point has negative height value
height.add(new int[]{b[0], -b[2]});
// end point has normal height value
height.add(new int[]{b[1], b[2]});
}

// sort $height, based on the first value, if necessary, use the second to
// break ties
Collections.sort(height, (a, b) -> {
if(a[0] != b[0])
return a[0] - b[0];
return a[1] - b[1];
});

// Use a maxHeap to store possible heights
Queue<Integer> pq = new PriorityQueue<>((a, b) -> (b - a));

// Provide a initial value to make it more consistent
pq.offer(0);

// Before starting, the previous max height is 0;
int prev = 0;

// visit all points in order
for(int[] h:height) {
if(h[1] < 0) { // a start point, add height
pq.offer(-h[1]);
} else { // a end point, remove height
pq.remove(h[1]);
}
int cur = pq.peek(); // current max height;

// compare current max height with previous max height, update result and
// previous max height if necessary
if(prev != cur) {
result.add(new int[]{h[0], cur});
prev = cur;
}
}
return result;
}

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

谢谢你,可爱的朋友。