[UVA] 105 Skyline

經典的一題，搞了我整整一天。原本以為是很簡單的scan line題，結果發現充滿了陷阱。

[TODO]

Skyline有多種解法。最容易implement的方法是暴力建1D array,因為X軸是int 最大才10000，所以建個int[10001]，讀每個building update 每格田度，最後iterate array畫出輪廓即可。

另一種是方法是scan line，可以應付任意X軸範 圍，而且不限定於int。簡單來說，就是在每次遇到新建築時才畫輪廓。我們可以maintain一個heap，記出到目前為止，還沒遇到右端點的buildings。然後在遇到新building時，把heap中其右端點位於新building左端點左邊的building pop掉，然後畫輪廓即可。

這題的陷阱是複數building可能會有同樣的左端點，於是這樣一來必需要要用多餘的一個heap記住目前還沒被丟到heap的buildings, 而在遇到不一樣左端點的building時，把暫時heap的東西pop出灌到normal heap中。