Given N buildings in a x-axis，each building is a rectangle and can be represented by a triple (start, end, height)，where start is the start position on x-axis, end is the end position on x-axis and height is the height of the building. Buildings may overlap if you see them from far away，find the outline of them。

An outline can be represented by a triple, (start, end, height), where start is the start position on x-axis of the outline, end is the end position on x-axis and height is the height of the outline.

Notice
Please merge the adjacent outlines if they have the same height and make sure different outlines cant overlap on x-axis.

Example
Given 3 buildings：

1
2
3
4
5
[
  [1, 3, 3],
  [2, 4, 4],
  [5, 6, 1]
]

The outlines are：

1
2
3
4
5
[
  [1, 2, 3],
  [2, 4, 4],
  [5, 6, 1]
]

这篇文章讲的很好：https://briangordon.github.io/2014/08/the-skyline-problem.html

我用的扫描线的方法，先把做为输入的区间拆分成点，按点的x坐标排序。 然后如果点是起始点，就把点的高度放入max heap, 如果是结束点就把点的高度删除，当max heap中最高的高度有变化的时候，说明outline有变化。

这里用的是普通的heap, 删除一个元素的时间复杂度为O(n)，为了优化时间复杂度，可以自己实现Hash Heap，删除操作可以做到O(logn)

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
class Point implements Comparable<Point> {
    int x;
    int isStart;
    int h;
    public Point(int x, int isStart, int h) {
        this.x = x;
        this.isStart = isStart;
        this.h = h;
    }
    @Override
    public int compareTo(Point that) {
        if (this.x != that.x)
            return this.x - that.x;
        return that.isStart - this.isStart;
    }
}
public ArrayList<ArrayList<Integer>> buildingOutline(int[][] buildings) {
    List<Point> list = new ArrayList<>();
    for (int[] b : buildings) {
        list.add(new Point(b[0], 1, b[2]));
        list.add(new Point(b[1], 0, b[2]));
    }
    Collections.sort(list);
    PriorityQueue<Integer> pq = new PriorityQueue<>(10, Collections.reverseOrder());
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    Point start = null;
    int height = 0;
    for (int i = 0; i < list.size(); i++) {
        Point p = list.get(i);
        if (p.isStart == 0) {
            pq.remove(p.h);
        } else {
            pq.add(p.h);
        }
        if (pq.isEmpty() || pq.peek() != height) {
            if (start != null && start.x != p.x) {
                ArrayList<Integer> l = new ArrayList<>();
                l.add(start.x);
                l.add(p.x);
                l.add(height);
                ans.add(l);
            }
            if (pq.isEmpty()) {
                start = null;
                height = 0;
            } else {
                start = p;
                height = pq.peek();
            }
        }
    }
    return ans;
}