# 218 Skyline Problem

input是大樓的最左位置、最右位置、高度: e.g. [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ]

output是list of 所有有高度改變的點 -> (高度改變的位置, 新高度)

Concept:

需要把所有建築物的起點終點記下來 -> List<int[]> height，並且照位置排序。

從左掃到右，怎麼知道高度有變化？prev 和 cur，前一個高度和新的高度。

怎麼知道cur有沒有變化？用Priority Queue來記錄目前經過的所有大樓高度，將所有entry用高度排序，由高往低，這樣取pq的最前面的entry就是現在的高度。

每次讀取到start point時就把該大樓的高度放入pq，讀到end point時就把該大樓的高度從pq移除，每次讀到新的位置都要檢查是否有高度改變，若有高度改變，就把(當前位置, 高度)存到list of ans中

Pseudocode:

List<int[]> result 用來存答案

List<int[]> height來存所有start point和end point，和該大樓的高度。區分start point和end point的方法是: start point的高度加上負號 e.g. (start point, -height), (end point, height)

for each element in buildings

height.add\(start point, -height\)

height.add\(end point, height\)

將List height依照位置排序，若位置相同，照高度排序。

宣告一個Priority Queue， pq，並自訂排序方法，高的排前面，

將0加入pq

int prev= 0 用來存前一個高度，比較高度有沒有改變

for each element in height

if\(h\[1\] < 0\) 則為start point, 將-h\[1\]加入pq

else 則為end point, 將h\[1\]從pq移除

int cur = pq.peek\(\); 當前高度即為pq最前面的entry

if cur != prev表示高度有改變

    result.add\(h\[0\], cur\)

    prev = cur

return result

完整程式碼:

public class Solution {
    //[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ]
    //[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> result = new ArrayList<>();
        List<int[]> height = new ArrayList<>();
        for(int[] b:buildings) {
            // start point has negative height value
            height.add(new int[]{b[0], -b[2]});
            // end point has normal height value
            height.add(new int[]{b[1], b[2]}); 
        }

        // sort $height, based on the first value, if necessary, use the second to
        // break ties
        Collections.sort(height, (a, b) -> {
                if(a[0] != b[0]) 
                    return a[0] - b[0];
                return a[1] - b[1];
        });

        // Use a maxHeap to store possible heights
        Queue<Integer> pq = new PriorityQueue<>((a, b) -> (b - a));

        // Provide a initial value to make it more consistent
        pq.offer(0);
        // Before starting, the previous max height is 0;
        int prev = 0;

        // visit all points in order
        for(int[] h:height) {
            if(h[1] < 0) { // a start point, add height
                pq.offer(-h[1]);
            } else {  // a end point, remove height
                pq.remove(h[1]);
            }
            int cur = pq.peek(); // current max height;

            // compare current max height with previous max height, update result and 
            // previous max height if necessary
            if(prev != cur) {
                result.add(new int[]{h[0], cur});
                prev = cur;
            }
        }
        return result;
    }
}