Description

Given N buildings in a x-axis，each building is a rectangle and can be represented by a triple (start, end, height)，where start is the start position on x-axis, end is the end position on x-axis and height is the height of the building. Buildings may overlap if you see them from far away，find the outline of them。

An outline can be represented by a triple, (start, end, height), where start is the start position on x-axis of the outline, end is the end position on x-axis and height is the height of the outline.

Notice

Please merge the adjacent outlines if they have the same height and make sure different outlines cant overlap on x-axis.

Example

Given 3 buildings：

[
  [1, 3, 3],
  [2, 4, 4],
  [5, 6, 1]
]

The outlines are：

[
  [1, 2, 3],
  [2, 4, 4],
  [5, 6, 1]
]

Solution

不能用依次两两merge interval来做，因为涉及到multiple interval的merge，必须要转换成edge来做。

给所有point排序，排序原则是：矮的start在前，高的end在前，start比end靠前
遍历point时用max heap存所有的高度, PriorityQueue变成max heap的方法就是存负值
将所有历史性的纵线存下来，通过和max heap中剩下的最大的高度对比来判断是不是历史性的纵线。注意存的height是接下来的height，所以存end的时候要判断接下来的height是不是0
最后遍历上一步存下来的start和end，画出最后的outline

注意这个comparator的写法。

public class Solution {
    /*
     * @param buildings: A list of lists of integers
     * @return: Find the outline of those buildings
     */
    public class Point {
        public int index;
        public int height;
        public boolean start;
        public Point(int index, int height, boolean start) {
            this.index = index;
            this.height = height;
            this.start = start;
        }
    }

    public Comparator<Point> PointComparator = new Comparator<Point> () {
        public int compare(Point a, Point b) {
            if (a.index != b.index) {
                return a.index - b.index;
            } 

            if (a.start && b.start) {
                return b.height - a.height;
            }

            if (!a.start && !b.start) {
                return a.height - b.height;
            }

            return a.start ? -1 : 1;
        }
    };

    public List<List<Integer>> buildingOutline(int[][] buildings) {
        // write your code here
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (buildings == null || buildings.length == 0 || buildings[0] == null || buildings[0].length == 0) {
            return result;
        }

        ArrayList<Point> points = new ArrayList<Point>(buildings.length * 2);
        for (int i = 0; i < buildings.length; i++) {
            points.add(new Point(buildings[i][0], buildings[i][2], true));
            points.add(new Point(buildings[i][1], buildings[i][2], false));
        }

        Collections.sort(points, PointComparator);

        PriorityQueue<Integer> heights = new PriorityQueue<Integer>(buildings.length);
        ArrayList<Point> outline = new ArrayList<Point>();
        for (Point point : points) {
            if (point.start) {
                if (heights.isEmpty() || point.height > -heights.peek()) {
                    outline.add(point);
                }
                heights.offer(-point.height);
            } else {
                heights.remove(-point.height);
                if (heights.isEmpty() || point.height > -heights.peek()) {
                    point.height = heights.isEmpty() ? 0 : -heights.peek();
                    outline.add(point);
                }
            }
        }

        int start = 0;
        int height = 0;
        for (Point point : outline) {
            if (height > 0) {
                result.add(new ArrayList<Integer>(Arrays.asList(start, point.index, height)));
            }

            start = point.index;
            height = point.height;
        }

        return result;
    }
}