Building Outline

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, 3, 3],
  [2, 4, 4],
  [5, 6, 1]
]

The outlines are：

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

class Node {
    int pos;
    int height;
    boolean isStart;
    public Node(int pos, int height, boolean isStart) {
        this.pos = pos;
        this.height = height;
        this.isStart = isStart;
    }
}
class NodeComparator implements Comparator<Node> {
    @Override
    public int compare(Node n1, Node n2) {
        if(n1.pos != n2.pos) {
            return n1.pos - n2.pos;
        }
        else if(n1.isStart && n2.isStart) {
            return n2.height - n1.height;
        }
        else if(!n1.isStart && !n2.isStart) {
            return n1.height - n2.height;
        }
        else {
            return n1.isStart ? -1 : 1;
        }
    }
}
public ArrayList<ArrayList<Integer>> buildingOutline(int[][] buildings) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    if (buildings == null || buildings.length == 0 || buildings[0].length == 0) {
        return res;
    }
    int m = buildings.length, col = buildings[0].length;
    List<Node> edges = new ArrayList<Node>();
    for (int i = 0; i < buildings.length; i++) {
        edges.add(new Node(buildings[i][0], buildings[i][2], true));
        edges.add(new Node(buildings[i][1], buildings[i][2], false));
    }
    Collections.sort(edges, new NodeComparator());
    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(m * col, Collections.reverseOrder());
    for (Node n : edges) {
        if(n.isStart) {
            if(maxHeap.isEmpty() || n.height > maxHeap.peek()) {
                ArrayList<Integer> item = new ArrayList<Integer>();
                item.add(n.pos);
                item.add(n.height);
                res.add(item);
            }
            maxHeap.offer(n.height);
        }
        else {
            maxHeap.remove(n.height);
            if (!maxHeap.isEmpty() && maxHeap.peek() < n.height) {
                ArrayList<Integer> item = new ArrayList<Integer>();
                item.add(n.pos);
                item.add(maxHeap.peek());
                res.add(item);
            }
            else if (maxHeap.isEmpty()) {
                ArrayList<Integer> item = new ArrayList<Integer>();
                item.add(n.pos);
                item.add(0);
                res.add(item);
            }
        }
    }
    return getResult(res);
}
public ArrayList<ArrayList<Integer>> getResult(ArrayList<ArrayList<Integer>> res) {
    if(res.size() == 0) {
        return res;
    }
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    int start = res.get(0).get(0);
    int height = res.get(0).get(1);
    for(int i = 1; i < res.size(); i++) {
        int end = res.get(i).get(0);
        if(height > 0) {
            ArrayList<Integer> item = new ArrayList<Integer>();
            item.add(start);
            item.add(end);
            item.add(height);
            ans.add(item);
        }
        start = end;
        height = res.get(i).get(1);
    }
    return ans;
}