public class Solution {
    public static class Line implements Comparable<Line> {
        public int index;
        public int height;
        public boolean isStart;

        @Override
        public int compareTo(Line arg0) {
            if (index != arg0.index)
                return index - arg0.index;
            return (arg0.isStart?arg0.height:-arg0.height)-(isStart?height:-height);

        }
    }
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> result = new ArrayList<int[]>();
        if (buildings == null || buildings.length == 0)
            return result;
        Line[] l = new Line[buildings.length * 2];
        for (int i = 0; i < buildings.length; i++) {
            l[i * 2] = new Line();
            l[i * 2].index = buildings[i][0];
            l[i * 2].height = buildings[i][2];
            l[i * 2].isStart = true;
            l[i * 2 + 1] = new Line();
            l[i * 2 + 1].index = buildings[i][1];
            l[i * 2 + 1].height = buildings[i][2];
            l[i * 2 + 1].isStart = false;
        }
        Arrays.sort(l);
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
        int height = 0;
        for (Line line : l) {
            if (line.isStart)
                pq.add(line.height);
            else
                pq.remove(line.height);
            int newH = pq.peek() == null ? 0 : pq.peek();
            if (newH != height) {
                height = newH;
                int[] re = new int[2];
                re[0] = line.index;
                re[1] = height;
                result.add(re);
            }
        }
        return result;
    }
}