1
class height implements Comparable<height> {
2
  int val = -1;
3
  int pos = -1;
4
  boolean isStart = false;
5

6
  height(int a, int b, boolean c) {
7
    val = a;
8
    pos = b;
9
    isStart = c;
10
  }
11

12
  public int compareTo(height h) {
13
    if (this.pos != h.pos) return this.pos - h.pos;
14
    if (isStart) return -1;
15
    if (h.isStart) return 1;
16

17
    return this.val - h.val;
18
  }
19
}
20

21
class Solution {
22
  public List<List<Integer>> getSkyline(int[][] buildings) {
23

24
    PriorityQueue<height> mQ = new PriorityQueue<>();
25
    int len = buildings.length;
26
    for (int[] b : buildings) {
27
      mQ.add(new height(b[2], b[0], true));
28
      mQ.add(new height(b[2], b[1], false));
29
    }
30
    PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
31
    heap.add(0);
32
    int prevHeight = 0;
33
    List<List<Integer>> res = new ArrayList<>();
34
    List<Integer> lst;
35
    while (mQ.size() > 0) {
36
      height h = mQ.poll();
37
      if (h.isStart) {
38
        heap.offer(h.val);
39
      } else {
40
        heap.remove(h.val);
41
      }
42

43
      if (prevHeight != heap.peek()) {
44
        lst = new ArrayList<>();
45
        lst.add(h.pos);
46

47
        if (res.size() > 0 && res.get(res.size() - 1).get(0) == h.pos) {
48
          lst.add(Math.max(heap.peek(), res.get(res.size() - 1).get(1)));
49
          res.remove(res.size() - 1);
50
        } else lst.add(heap.peek());
51
        res.add(lst);
52
        prevHeight = heap.peek();
53
      }
54
    }
55
    return res;
56
  }
57
}