Skyline

public class Solution {
    /**
     * @param buildings: A list of lists of integers
     * @return: Find the outline of those buildings
     */

    class Edge {
        int pos;
        int height;
        boolean isStart;
        public Edge(int pos, int height, boolean isStart) {
            this.pos = pos;
            this.height = height;
            this.isStart = isStart;
        }
    }

    public ArrayList<ArrayList<Integer>> buildingOutline(int[][] buildings) {
        // write your code here
         ArrayList<int[]> res = new ArrayList<int[]>();
         ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>();
        if (buildings == null || buildings.length == 0 || buildings[0].length == 0) {
            return temp;
        }
        ArrayList<Edge> edges = new ArrayList<Edge>();
        // put start edge and end edge to list
        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
        Collections.sort(edges, new Comparator<Edge>(){
            public int compare(Edge l1, Edge l2) {
                // first compare position, asc
                if (l1.pos != l2.pos)
                    return Integer.compare(l1.pos, l2.pos);
                // compare height if both are start, reverse order    
                if (l1.isStart && l2.isStart) {
                    return Integer.compare(l2.height, l1.height);
                }
                // compare height if both are end, reverse order
                if (!l1.isStart && !l2.isStart) {
                    return Integer.compare(l1.height, l2.height);
                }
                // start comes first
                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 output(res);
    }

    public ArrayList<ArrayList<Integer>> output(ArrayList<int[]> res) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
        if (res.size() > 0) {
          int pre = res.get(0)[0];
          int height = res.get(0)[1];
          for (int i = 1; i < res.size(); i++) {
            ArrayList<Integer> now = new ArrayList<Integer>();
            int id = res.get(i)[0];
            if (height > 0) {
              now.add(pre);
              now.add(id);
              now.add(height);
              ans.add(now);
            }
            pre = id;
            height = res.get(i)[1];
      }
    }
    return ans;
  }


}