返回信息流没想到才刚投了微信的暑期实习，就被抓去面试了。今天面试的一个算法题把我难住了，做了半天都没有做出来（哭），求大神指点：
就是说一个平地上有很多的房子，这个每个房子有一个高度，还有它的起始和终止的位置。然后现在有一束光是从它们的正面照过去的，矮的房子就会被高的遮盖了，最后求出投影的轮廓高度。我大概画了一下图（上传到了文件里）。
外面的黄线就是最后要求的轮廓。
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #92159同步于 2017/3/8
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【问题】微信面试题，求大神指点！
echo820
2017/3/8镜像同步89 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
扫描线吧
似乎是经典问题
http://img.blog.csdn.net/20170308213204304?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMzAwNzkwMA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
但是这道题应该是简化版本的，应该有更简单的做法？
这题应该用扫描线来做：
我们将每一个建筑的起点和终点分别标注以后排序，然后开始扫描来查看每个建筑的高度。
这样的情况下，我们需要判断当前最高的建筑是哪个，然后该点的建筑高度则为高的那个。但是当同一时刻有两个以上建筑甚至很多的建筑的时候，就比较麻烦了。
这时候就需要引入堆(heap)的思路来做，当遇到“头”节点时候，记录该建筑的高度，然后把这个node放入堆中，node的结构为(建筑id，index，高度，是否为“头”节点)。然后遇到重合节点，则需要取出堆的最大值即可，最后当遇到“尾”节点的时候，则把这个node从堆中删除。
当然，堆是可以删除其中的最大值的，但是并不能去除其中的某个特定节点，如上图当蓝线扫出“内部”的建筑时，则需要弹出“内部”的建筑，而不是把此时堆顶最大值的“外部”建筑弹出。
对于这个问题，Java小伙伴可以用priority_queue的remove操作或者也可以自己实现hash heap来解决，而C++小伙伴只能用map来实现这样的数据结构了，因为map本身是平衡二叉树，其中自带remove操作。
我用C++的multiset实现了一下。
BTW, 推荐一个公众号，他们会定期发送一些面试算法的知识“光影键盘侠”。上面就有这个题好像，请叫我雷锋！
[ema0][ema0]
学习了
【 在 tkw1110 的大作中提到: 】
: 这题应该用扫描线来做：
: [upload=2][/upload]
: 我们将每一个建筑的起点和终点分别标注以后排序，然后开始扫描来查看每个建筑的高度。
: ...................
哇 好棒 好详细 感谢~
【 在 tkw1110 的大作中提到: 】
: 这题应该用扫描线来做：
: [upload=2][/upload]
: 我们将每一个建筑的起点和终点分别标注以后排序，然后开始扫描来查看每个建筑的高度。
: ...................