注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex218 The Skyline Problem  

2015-05-31 17:37:14|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

Buildings Skyline Contour

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

  • The number of buildings in any input list is guaranteed to be in the range [0, 10000].
  • The input list is already sorted in ascending order by the left x position Li.
  • The output list must be sorted by the x position.
  • There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]

比较难的新题,其实这题真要是自己亲手写的话还是能做出来的,不过肯定代码是特别恶心的,没有别人用mutilset写的简洁明了。这题和interval和merge intervals那两道题还是挺像的,参考里面的百草园他的博客真是写的很不错。

里面用到mutilset的数据结构,看名字就能直到,里面是可以允许重复元素出现的,并且每次插入后就自动排序了,删除操作也很简单。另外作者的小技巧很棒,用高度的负值来表示左边界,右边界正常表示,这样就少维护一个属性了。先给所有的interval排序,按顺序比较,保存一下前一个高度和当前的高度,一旦不一样,说明遇到拐点了,就可以往结果里面保存了。遇到左边界,说明是起始,需要往堆里面插入,遇到右边界,说明这个高度的使命完成了,可以删除了。
代码

/*
* 我觉得,这一题要是不用高级的数据结构肯定得恶心死
* merge interval 那一题就是这个样子,自己确定下标可以但是需要做大量的判断
* 参考网上的思路
*/
class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
vector<pair<int, int>> height;
for (auto &b : buildings)
{
height.push_back({ b[0], -b[2] });
//左节点存为负值,这样在后面就不需要判定到底是右边界还是左边界了
height.push_back({ b[1], b[2] });
}
//先按照x坐标排序,高度不参与
sort(height.begin(), height.end());
multiset<int> heap;
heap.insert(0);

vector<pair<int, int>> res;
int pre = 0, cur = 0;
for (auto &h : height)
{
//遍历所有的高度
if (h.second < 0)
{
//遇到左边界就插入高度
heap.insert(-h.second);
}
else
{
//遇到右边界就删除高度
heap.erase(heap.find(h.second));
}
/*
* 在这里举一个例子 [0,3] [2,2] [3,3 [5,2]
* 实际height里面是这么存的 [0,-3] [2,-2] [3,3] [5,2]
* 遇到第一个高度 插入cur =0, heap 里面存{0 3}, 结果里面存了一个[0,3]点
* 遇到第二个高度 (2,-2)插入,heap 里面存{ 0,2,3},cur =3,pre =3; 相等,结果 [0,3]
* 遇到第三个高度,删除高度3 ,heap里面存{0,2},cur = 2,pre=3,不等结果存[0,3] [3,2]
* 遇到第四个,删除高度2 ,cur =0,pre =2 不等,结果存[0,3] [3,2][0,0]
*/
cur = *heap.rbegin();
if (cur != pre)
{
res.push_back({ h.first, cur });
pre = cur;
}
}
return res;
}
};



参考
http://www.cnblogs.com/easonliu/p/4531020.html
https://briangordon.github.io/2014/08/the-skyline-problem.html
http://www.cnblogs.com/grandyang/p/4534586.html
  评论这张
 
阅读(75)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017