Id1011
TitleThe Skyline Problem
Tagsbrute force
simulation
sweep line
Brief solution虽然直接暴力模拟可以过掉这题,但是还是推荐有扫描线写一下:首先为所有的building生成事件,事件有开始值和结束值。然后按从小到大的顺序访问所有可能的值。对于当前访问到的值,将所有开始值不超过当前访问值的事件取出来,将(event.height, event.right)放到优先队列中。接着从这个优先队列中找出最高的building,当优先队列的top元素的第二个分量不超过当前访问值时,直接将这个元素从优先队列中移除,否则记录这个元素的值并且找最高building的算法结束。这个时候当前访问值和最高building就是一组解。当然,要注意没有找到最高building的情况,还要注意当前的height和已经找到的上一个height相同的情况。
time usage:1.031313