218. The Skyline Problem

package com.chanmufeng.questions;
import java.util.*;

public class Skyline {
    public static class Node {
        public int pos;
        public int height;
        public boolean isUp;

        public Node(int pos, int height, boolean isUp) {
            this.pos = pos;
            this.height = height;
            this.isUp = isUp;
        }

        @Override
        public String toString() {
            return "[" + pos + " " + height + " " + isUp + "]";
        }
    }

    public static class NodeComparator implements Comparator<Node> {
        @Override
        public int compare(Node o1, Node o2) {
            //如果位置不相等，将位置升序
            if (o1.pos != o2.pos) {
                return o1.pos - o2.pos;
            }
            //如果位置相等，优先排列下降的位置
            if (o1.isUp != o2.isUp) {
                return o1.isUp ? 1 : -1;
            }
            return 0;
        }
    }

    public static List<int[]> getSkyline(int[][] buildings) {
        Node[] nodes = new Node[buildings.length * 2];
        int index = 0;
        for (int i = 0; i < buildings.length; i++) {
            nodes[index++] = new Node(buildings[i][0], buildings[i][2], true);
            nodes[index++] = new Node(buildings[i][1], buildings[i][2], false);
        }
        Arrays.sort(nodes, new NodeComparator());

        //key：高度 value：高度出现的次数
        TreeMap<Integer, Integer> htMap = new TreeMap<>();
        //key:position value:该位置的最高高度
        TreeMap<Integer, Integer> pmMap = new TreeMap<>();

        List<int[]> res = new LinkedList<>();

        for (int i = 0; i < nodes.length; i++) {

            if (nodes[i].isUp) {
                if (!htMap.containsKey(nodes[i].height)) {
                    htMap.put(nodes[i].height, 1);
                } else {
                    htMap.put(nodes[i].height, htMap.get(nodes[i].height) + 1);
                }
            } else {
                if (htMap.get(nodes[i].height) == 1) {
                    htMap.remove(nodes[i].height);
                } else {
                    htMap.put(nodes[i].height, htMap.get(nodes[i].height) - 1);
                }
            }

            if (htMap.isEmpty()) {
                pmMap.put(nodes[i].pos, 0);
            } else {
                pmMap.put(nodes[i].pos, htMap.lastKey());
            }
        }

        int height = 0;
        Iterator it = pmMap.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry entry = (Map.Entry) it.next();
            int curMaxHeight = (int) entry.getValue();
            if (height != curMaxHeight) {
                int[] temp = new int[2];
                temp[0] = (int) entry.getKey();
                temp[1] = curMaxHeight;
                ((LinkedList<int[]>) res).addLast(temp);
                height = curMaxHeight;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] arr = {
                {2, 9, 10},
                {3, 7, 15},
                {5, 12, 12},
                {15, 20, 10},
                {19, 24, 8},
        };
//        int[][] arr = {
//                {1, 3, 3},
//                {2, 4, 2},
//                {4, 5, 1},
//        };
        List res = getSkyline(arr);
        for (int i = 0; i < res.size(); i++) {
            for (int item : (int[]) res.get(i)) {
                System.out.print(item + " ");
            }
            System.out.println();
        }
    }
}