🥹218 The Skyline Problem

https://leetcode.com/problems/the-skyline-problem/

key idea是把它们都看作点，遇到start就记录高度，遇到end就剔除高度，然后看遇到每个可能的转折点时的最大高度值

skyline其实就是每个区间里最高的值，换个角度想每一个当前最高的值只会在对应的区间出现，而这个值只会在转折处发生改变。

似乎也可以用线段树做

also seen in TreeMap section

class Solution {
    class Point {
        public int x;
        public boolean start;
        public int height;
        public Point(int x, boolean s, int h) {
            this.x = x;
            this.start = s;
            this.height = h;
        }
    }
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> res = new ArrayList<>();
        // x coord -> point
        TreeMap<Integer, List<Point>> map = new TreeMap<>();
        // 把building的起止端各自当作节点存进map里
        for (int i = 0; i < buildings.length; i++) {
            List<Point> list = map.get(buildings[i][0]);
            if (list == null) {
                list = new ArrayList<>();
            }
            list.add(new Point(buildings[i][0], true, buildings[i][2]));
            map.put(buildings[i][0], list);
            
            list = map.get(buildings[i][1]);
            if (list == null) {
                list = new ArrayList<>();
            }
            list.add(new Point(buildings[i][1], false, buildings[i][2]));
            map.put(buildings[i][1], list);
        }
        // height -> number of points that has this height
        TreeMap<Integer, Integer> heights = new TreeMap<>(Collections.reverseOrder());
        // 按横坐标从左往右遍历所有point，更新高度记录，which只会在segment start和end的时候变化
        for (Map.Entry<Integer, List<Point>> entry : map.entrySet()) {
            for (Point p : entry.getValue()) {
                int height = p.height;
                // starting point就把height加入高度记录中
                if (p.start) {
                    int cnt = heights.getOrDefault(p.height, 0);
                    heights.put(p.height, cnt + 1);
                } else {
                // ending point就把height从高度记录中扣除  
                    int cnt = heights.get(p.height);
                    if (cnt == 1) {
                        heights.remove(p.height);
                    } else {
                        heights.put(p.height, cnt - 1);
                    }
                }
            }
            // 更新之后记录当前点的最大height
            int h = heights.isEmpty()? 0 : heights.firstKey();
            // 合并一下高度一样的的
            if (res.isEmpty() || res.get(res.size() - 1).get(1) != h) {
                res.add(Arrays.asList(new Integer[]{entry.getKey(), h}));
            }
        }
        return res;
    }
}