Building Outline

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.

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:

Same problem like Number of Airplanes in the Sky. For a triple, we convert it to (index, height, isStart) format. (1, 3, 3) => (1, 3, true) and (3, 3, false). We put these new format of data in a PriorityQueue which sorts them based on index and then isStart. From the smallest index to the largest index, we could always push (index, height, isStart) into a max PriorityQueue which will give us the largest height at this moment as the outline. When one building is finished (isStart == false is triggered), we need to remove this height from the max PriorityQueue.

Code:

public class Solution {
    /**
     * @param buildings: A list of lists of integers
     * @return: Find the outline of those buildings
     */
    public ArrayList<ArrayList<Integer>> buildingOutline(int[][] buildings) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (buildings == null || buildings.length == 0 || buildings[0].length == 0) {
            return res;
        }
        int m = buildings.length;
        Queue<Event> eventQ = new PriorityQueue<Event>(m * 2);
        for (int[] building : buildings) {
            eventQ.offer(new Event(building[0], building[2], true));
            eventQ.offer(new Event(building[1], building[2], false));
        }
        Queue<Integer> heightQ = new PriorityQueue<Integer>(m, Collections.reverseOrder());

        int start = 0;
        int lastH = 0;
        while (!eventQ.isEmpty()) {
            Event e = eventQ.poll();
            if (e.isStart) {
                heightQ.offer(e.val);
            } else {
                heightQ.remove(e.val);
            }
            int h = 0;
            if (!heightQ.isEmpty()) {
                h = heightQ.peek();
            }

            if (h != lastH) {
                if (lastH > 0 && e.idx > start) {
                    ArrayList<Integer> temp = new ArrayList<>();
                    temp.add(start);
                    temp.add(e.idx);
                    temp.add(lastH);
                    res.add(temp);
                }
                start = e.idx;
                lastH = h;
            }
        }
        return res;
    }

    class Event implements Comparable<Event> {
        int idx;
        int val;
        boolean isStart;
        public Event(int index, int value, boolean start) {
            idx = index;
            val = value;
            isStart = start;
        }
        @Override public int compareTo(Event that) {
            if (this.idx != that.idx) {
                return this.idx - that.idx;
            }
            if (this.isStart && !that.isStart) {
                return -1;
            } else if (!this.isStart && that.isStart) {
                return 1;
            } else {
                return 0;
            }
        }
        @Override public String toString() {
            return idx + " " + val + " " + isStart;
        }
    }
}