-
Notifications
You must be signed in to change notification settings - Fork 2
/
TheSkylineProblem.java
82 lines (72 loc) · 2 KB
/
TheSkylineProblem.java
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
package com.algorithm.playground.leetcode.problems.lc200.lc210.lc218;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
/**
* https://leetcode.com/problems/the-skyline-problem/description/
*/
public class TheSkylineProblem {
class Solution {
public List<int[]> getSkyline(int[][] buildings) {
LinkedList<Node> list = new LinkedList<>();
list.add(new Node(0, Integer.MAX_VALUE, 0));
for (int[] b : buildings) {
insert(list, b);
}
List<int[]> ans = new ArrayList<>();
int height = 0;
for (Node curr : list) {
if (curr.height > height) {
ans.add(new int[]{curr.left, curr.height});
height = curr.height;
} else if (curr.height < height) {
ans.add(new int[]{curr.left - 1, curr.height});
height = curr.height;
}
}
if (list.getLast().height > 0) {
ans.add(new int[]{Integer.MAX_VALUE, 0});
}
return ans;
}
private void insert(LinkedList<Node> list, int[] building) {
int li = building[0], ri = building[1], hi = building[2];
ListIterator<Node> iterator = list.listIterator();
while (iterator.hasNext()) {
Node curr = iterator.next();
if (curr.left > ri) {
break;
} else if (curr.right >= li && curr.height < hi) {
int left = li - curr.left;
int right = curr.right - ri;
if (left > 0) {
iterator.set(new Node(curr.left, li - 1, curr.height));
iterator.add(new Node(li, Math.min(ri, curr.right), hi));
} else {
iterator.set(new Node(li - left, Math.min(ri, curr.right), hi));
}
if (right > 0) {
iterator.add(new Node(ri + 1, curr.right, curr.height));
}
}
}
}
private class Node {
int left, right, height;
public Node(int left, int right, int height) {
this.left = left;
this.right = right;
this.height = height;
}
@Override
public String toString() {
return "Node{" +
"left=" + left +
", right=" + right +
", height=" + height +
'}';
}
}
}
}