-
Notifications
You must be signed in to change notification settings - Fork 0
/
SkyLine.java
77 lines (74 loc) · 2.07 KB
/
SkyLine.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
public class SkyLine {
public List<List<Integer>> getSkyline(int[][] buildings) {
List<List<Integer>> res = new ArrayList<>();
if (buildings == null || buildings.length == 0) return res;
PriorityQueue<Building> maxHeap = new PriorityQueue<>();
List<Point> points = new ArrayList<>();
for (int[] building : buildings) {
Building cur = new Building(building[0], building[1], building[2]);
points.add(new Point(cur.start, 0, cur));
points.add(new Point(cur.end, 1, cur));
}
Collections.sort(points);
int prevHeight = 0;
for (Point p : points) {
if (p.state == 0) {
maxHeap.offer(p.building);
} else {
while (!maxHeap.isEmpty() && maxHeap.peek().end <= p.position) {
maxHeap.poll();
}
}
int curHeight = maxHeap.isEmpty() ? 0 : maxHeap.peek().height;
if (curHeight != prevHeight) {
res.add(new ArrayList<>(Arrays.asList(p.position, curHeight)));
}
prevHeight = curHeight;
}
return res;
}
static class Point implements Comparable<Point> {
int position;
int state; // 0: start 1: end
Building building;
Point(int position, int state, Building building) {
this.position = position;
this.state = state;
this.building = building;
}
@Override
public int compareTo(Point other) {
int res = Integer.compare(this.position, other.position);
if (res == 0) {
int stateCompare = Integer.compare(this.state, other.state);
if (stateCompare == 0) {
return Integer.compare(other.building.height, this.building.height);
}
return stateCompare;
}
return res;
}
}
static class Building implements Comparable<Building> {
int start;
int end;
int height;
Building(int start, int end, int height) {
this.start = start;
this.end = end;
this.height = height;
}
@Override
public int compareTo(Building other) {
int res = Integer.compare(other.height, this.height);
if (res == 0) {
int startCompare = Integer.compare(this.start, other.start);
if (startCompare == 0) {
return Integer.compare(this.end, other.end);
}
return startCompare;
}
return res;
}
}
}