Skyline Problem【难】

这道题的描述就给人一种很难的感觉。但是我其实觉得有些ez，medium的看起来更恐怖。这种我人眼知道怎么算的感觉都没有那么恐怖。

第一想法从左边开始看，首先计算第一个building 的leftmost point= 它的高。 然后进入第二个building。如果和之前那个building的地盘有重叠，那么他的高将会是新的point的Y。 和之前building的intesection where one starts/ one ends为新的point的x。

如果两个building没有重叠。 那么就是各自building起点， 终点。

我还是比较满意我这个答案的，不足的地方是没有考虑到同一个region累加的问题。 同一个region或者region范围内加东西简直太恶心了。。。

九章算法：

https://mp.weixin.qq.com/s?__biz=MzA5MzE4MjgyMw==&mid=2649454957&idx=1&sn=3a490c35f06951b287f8e0595483a164&mpshare=1&scene=1&srcid=0317g16NhnkjjN6volM2eDMS&key=5657e61c2ec7753de5eb6df309c0551cdeaedf5566d7cf8600a14b81f5374d104111c7d26e644e96a1f436719c13bebaa0c5d38daa1a59d6ec4b11ece25a362b8ae43646043d0c218139014312fa4934&ascene=0&uin=MTUyMzg3NjAwMA%3D%3D&devicetype=iMac+MacBookAir7%2C1+OSX+OSX+10.12.3+build(16D32)&version=12020010&nettype=WIFI&fontScale=100&pass_ticket=0AiIToHJN8yqpuqRAsA5PaaQMJr8KtvlnZ2EqkX0zx%2BEZweRvHKyF%2ByjmycpUbVn

今天看九章算法，发现 扫描线就是为这题而生的。似乎和count飞机那题也是一样。

视频参考： https://briangordon.github.io/2014/08/the-skyline-problem.html

经过一个多小时的奋斗，终于做出来了！ 成就感爆棚有木有！！！

详解：

主要考虑的几个case

1. 完全的叠加。 2.挨着的。3. 中间有空隙的。 4.

解决叠加，化简问题是我觉得这次写的算法最了不起的地方。把所有重叠width的方块里只取它最高height的方块保留下来。具体做法是在遍历building的时候，每次检查一下上一个 added 的方块是不是start和这个start一样，end跟这个end一样。如果是 就比较一下height，谁大保留谁。 

另一个核心算法是 扫描线。 在这题里发挥着很大的作用。 把start, end分开。 然后把Time object 排序。 然后我们每见到一个start就把height加入queue. 每见到一个end 就把之前的pop出来。 碰到end的时候有许多case需要考虑。比如说如果没有人挨着的话，就应该add[position, height=0]. 如果有人挨着的话，看对方Height来决定怎么处理。