Leetcode: The Skyline Problem & Lintcode: Building Outline

把每一个building拆成两个edge，一个入一个出。所有的edge加入到一个list中。再对这个list进行排序，排序顺序为：如果两个边的position不一样，那么按pos排，否则根据edge是入还是出来排。
根据position从前到后扫描每一个edge，将edge根据是入还是出来将当前height加入或者移除heap。再得到当前最高点来决定是否加入最终结果。非常巧妙，值得思考。

public class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> res = new ArrayList<int[]>();
        if (buildings == null || buildings.length == 0 || buildings[0].length == 0) {
            return res;
        }
        List<Edge> edges = new ArrayList<Edge>();
        for (int[] building : buildings) {
            Edge startEdge = new Edge(building[0], building[2], true);
            edges.add(startEdge);
            Edge endEdge = new Edge(building[1], building[2], false);
            edges.add(endEdge);
        }
        //sort edges according to position, height, and if the edge is start or end
        edges.sort(new Comparator<Edge>(){
            public int compare(Edge l1, Edge l2) {
                if (l1.pos != l2.pos)
                    return Integer.compare(l1.pos, l2.pos);
                if (l1.isStart && l2.isStart) {
                    return Integer.compare(l2.height, l1.height);
                }
                if (!l1.isStart && !l2.isStart) {
                    return Integer.compare(l1.height, l2.height);
                }
                return l1.isStart ? -1 : 1;
            }
        });
        //heap of height
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>(10, Collections.reverseOrder());
        for (Edge edge : edges) {
            if (edge.isStart) {
                if (heap.isEmpty() || edge.height > heap.peek()) {
                    res.add(new int[]{edge.pos, edge.height});
                }
                heap.add(edge.height);
            } else {
                heap.remove(edge.height);
                if (heap.isEmpty() || edge.height > heap.peek()) {
                    res.add(heap.isEmpty() ? new int[]{edge.pos,0} : new int[]{edge.pos, heap.peek()});
                }
            }
        }
        return res;
    }
    class Edge implements Comparable<Edge>{
        int pos;
        int height;
        boolean isStart;
        public Edge(int pos, int height, boolean isStart) {
            this.pos = pos;
            this.height = height;
            this.isStart = isStart;
        }
    }
}