LeetCode - The Skyline Problem
Problem description
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], …]
Analysis
Basically we can split the building into two lines, one is start of the building and one is the end of the building. And draw the skyline one by one.
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
PriorityQueue<Node> pq = new PriorityQueue<>((o1,o2)-> {
if (o1.x != o2.x)
return o1.x - o2.x;
else{
if(o1.isStart&&o2.isStart){
return o2.h-o1.h;
}else if(!o1.isStart&&!o2.isStart){
return o1.h-o2.h;
}else{
return o1.isStart? -1:1;
}
}
});
for (int[] info:buildings){
pq.offer(new Node(info[0], info[2], true));
pq.offer(new Node(info[1], info[2], false));
}
List<List<Integer>> res = new ArrayList<>();
PriorityQueue<Integer> maxheap = new PriorityQueue<>((o1, o2)->{
return o2-o1;
});
while(!pq.isEmpty()){
List<Integer> list = new ArrayList<>();
Node node = pq.poll();
list.add(node.x);
if (node.isStart){
int maxheight = maxheap.isEmpty()? 0:maxheap.peek();
if(node.h>maxheight){
list.add(node.h);
res.add(list);
}
maxheap.offer(node.h);
}
else{
maxheap.remove(node.h);
int maxheight = maxheap.isEmpty()? 0:maxheap.peek();
if(maxheight<node.h){
list.add(maxheight);
res.add(list);
}
}
}
return res;
}
class Node{
int x;
int h;
boolean isStart;
public Node(int _x, int _h, boolean is){
x = _x;
h = _h;
isStart = is;
}
}
}
Another approach is to use divide and conquer.
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
class Solution {
/**
* Divide-and-conquer algorithm to solve skyline problem,
* which is similar with the merge sort algorithm.
*/
public List<List<Integer>> getSkyline(int[][] buildings) {
int n = buildings.length;
List<List<Integer>> output = new ArrayList<List<Integer>>();
// The base cases
if (n == 0) return output;
if (n == 1) {
int xStart = buildings[0][0];
int xEnd = buildings[0][1];
int y = buildings[0][2];
output.add(new ArrayList<Integer>() { {add(xStart); add(y); } });
output.add(new ArrayList<Integer>() { {add(xEnd); add(0); } });
// output.add(new int[]{xStart, y});
// output.add(new int[]{xEnd, 0});
return output;
}
// If there is more than one building,
// recursively divide the input into two subproblems.
List<List<Integer>> leftSkyline, rightSkyline;
leftSkyline = getSkyline(Arrays.copyOfRange(buildings, 0, n / 2));
rightSkyline = getSkyline(Arrays.copyOfRange(buildings, n / 2, n));
// Merge the results of subproblem together.
return mergeSkylines(leftSkyline, rightSkyline);
}
/**
* Merge two skylines together.
*/
public List<List<Integer>> mergeSkylines(List<List<Integer>> left, List<List<Integer>> right) {
int nL = left.size(), nR = right.size();
int pL = 0, pR = 0;
int currY = 0, leftY = 0, rightY = 0;
int x, maxY;
List<List<Integer>> output = new ArrayList<List<Integer>>();
// while we're in the region where both skylines are present
while ((pL < nL) && (pR < nR)) {
List<Integer> pointL = left.get(pL);
List<Integer> pointR = right.get(pR);
// pick up the smallest x
if (pointL.get(0) < pointR.get(0)) {
x = pointL.get(0);
leftY = pointL.get(1);
pL++;
}
else {
x = pointR.get(0);
rightY = pointR.get(1);
pR++;
}
// max height (i.e. y) between both skylines
maxY = Math.max(leftY, rightY);
// update output if there is a skyline change
if (currY != maxY) {
updateOutput(output, x, maxY);
currY = maxY;
}
}
// there is only left skyline
appendSkyline(output, left, pL, nL, currY);
// there is only right skyline
appendSkyline(output, right, pR, nR, currY);
return output;
}
/**
* Update the final output with the new element.
*/
public void updateOutput(List<List<Integer>> output, int x, int y) {
// if skyline change is not vertical -
// add the new point
if (output.isEmpty() || output.get(output.size() - 1).get(0) != x)
output.add(new ArrayList<Integer>() { {add(x); add(y); } });
// if skyline change is vertical -
// update the last point
else {
output.get(output.size() - 1).set(1, y);
}
}
/**
* Append the rest of the skyline elements with indice (p, n)
* to the final output.
*/
public void appendSkyline(List<List<Integer>> output, List<List<Integer>> skyline,
int p, int n, int currY) {
while (p < n) {
List<Integer> point = skyline.get(p);
int x = point.get(0);
int y = point.get(1);
p++;
// update output
// if there is a skyline change
if (currY != y) {
updateOutput(output, x, y);
currY = y;
}
}
}
}