1 public class Solution {
2 static int li(int[] building){
3 return building[0];
4 }
5
6 static int ri(int[] building){
7 return building[1];
8 }
9
10 static int hi(int[] building){
11 return building[2];
12 }
13
14 static class SortedBuilds {
15 int[][] buildings;
16 int p = 0;
17
18 PriorityQueue<int[]> inserted = new PriorityQueue<>((a, b) -> li(a) - li(b));
19
20 SortedBuilds(int[][] buildings) {
21 this.buildings = buildings;
22 }
23
24 boolean hasNext(){
25 return p < buildings.length || !inserted.isEmpty();
26 }
27
28
29 int[] next(){
30
31 if(p < buildings.length && !inserted.isEmpty()){
32
33 if(li(buildings[p]) < li(inserted.peek())){
34 return buildings[p++];
35 }else{
36 return inserted.poll();
37 }
38
39 } else if(p < buildings.length ){
40 return buildings[p++];
41 } else { // !inserted.isEmpty())
42 return inserted.poll();
43 }
44
45 }
46
47 void insert(int[] building){
48 inserted.add(building);
49 }
50 }
51
52 public List<int[]> getSkyline(int[][] buildings) {
53
54 List<int[]> all = new ArrayList<>();
55 if(buildings.length == 0) return all;
56
57 SortedBuilds sortedBuilds = new SortedBuilds(buildings);
58
59 int[] a = sortedBuilds.next();
60
61 while (sortedBuilds.hasNext()){
62 int[] b = sortedBuilds.next();
63
64 if(ri(a) == li(b) && hi(a) == hi(b)){
65 a = new int[]{li(a), ri(b), hi(a)};
66 continue;
67 }
68
69 // a.r b.l
70 if(ri(a) <= li(b)){
71 all.add(new int[]{li(a), hi(a)});
72
73 if(ri(a) < li(b)){
74 all.add(new int[]{ri(a), 0});
75 }
76
77 a = b;
78 continue;
79 }
80
81 // a.l b.l
82 if(li(a) == li(b)){
83
84 // make a higher than b
85 if(hi(a) < hi(b)){
86 sortedBuilds.insert(a);
87 a = b;
88 continue;
89 }
90
91 if(ri(a) < ri(b)){
92 sortedBuilds.insert(new int[]{ri(a), ri(b), hi(b)});
93 }
94 // else drop b (b inside a)
95 continue;
96 }
97
98 //
99 if(hi(a) < hi(b)){
100
101 all.add(new int[]{li(a), hi(a)});
102
103 if(ri(a) > ri(b)){
104 sortedBuilds.insert(new int[]{ri(b), ri(a), hi(a)});
105 }
106
107 a = b;
108 continue;
109 }
110
111 // a.h >= b.h
112
113 if(ri(a) < ri(b)){
114 sortedBuilds.insert(new int[]{ri(a), ri(b), hi(b)});
115 }
116 // else drop b (b inside a)
117 }
118
119 all.add(new int[]{li(a), hi(a)});
120 all.add(new int[]{ri(a), 0});
121
122 return all;
123 }
124 }