The Skyline Problem

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] . And the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

• Time: O(n)
• Space: O(n)

public List<int[]> getSkyline(int[][] buildings) {
    List<int[]> ret = new ArrayList<>(), list = new ArrayList<>();
    for (int[] b : buildings) {
        list.add(new int[]{b[0], -b[2]});
        list.add(new int[]{b[1], b[2]});
    }
    Collections.sort(list, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[0] == o2[0] ? o1[0] - o2[0] : o1[1] - o2[1];
        }
    });
    TreeMap<Integer, Integer> heap = 
        new TreeMap<Integer, Integer>(Collections.reverseOrder());
    heap.put(0, 1);
    int preHeight = 0;
    for (int[] b : list) {
        if (b[1] < 0) {
            Integer count = heap.get(-b[1]);
            count = count == null ? 1 : count + 1;
            heap.put(-b[1], count);
        } else {
            Integer count = heap.get(b[1]) - 1;
            if (count == 0) {
                heap.remove(b[1]);
            } else {
                heap.put(b[1], count);
            }
        }
        int curHeight = heap.firstKey();
        if (curHeight != preHeight) {
            ret.add(new int[]{b[0], curHeight});
            preHeight = curHeight;
        }
    }
    return ret;
}