请教一道题：skyline - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一道题：skyline

请教一道题：skyline# JobHunting - 待字闺中

y*82014-10-21 07:10

1 楼

各位大神，请教这个老题目skyline。之前有帖子提过
http://www.mitbbs.com/article_t1/JobHunting/32579865_0_1.html
http://www.mitbbs.com/article_t/JobHunting/32569901.html
但是没有看懂解答。
一堆interval，带有start和end，以及高度，整合之后，请输出每个时间段及这个时
间段内最大的高度。
Example Input：
S1: {[2,5], vol=10}, {[6,10], vol=2}
S2: {[1,6], vol=1}, {[8,12], vol=8}
Example Output:
[1,2],vol=1, [2,5], vol=10, [5,6], vol = 1, [6,8], vol = 2, [8,12], vol = 8.
我的思路是先对start排序，按照sorted的顺序入min heap，每次入的时候按照end坐标
弹出heap中的最早结束的interval。但是怎么分段和计算最大高度，我就想不出来了。
先谢谢各位大神了！

j*y2014-10-21 07:10

2 楼

http://elementsofprogramminginterviews.com/solutions/
search "draw the skyline"

【在 y*******8 的大作中提到】

: 各位大神，请教这个老题目skyline。之前有帖子提过
: http://www.mitbbs.com/article_t1/JobHunting/32579865_0_1.html
: http://www.mitbbs.com/article_t/JobHunting/32569901.html
: 但是没有看懂解答。
: 一堆interval，带有start和end，以及高度，整合之后，请输出每个时间段及这个时
: 间段内最大的高度。
: Example Input：
: S1: {[2,5], vol=10}, {[6,10], vol=2}
: S2: {[1,6], vol=1}, {[8,12], vol=8}
: Example Output:

l*a2014-10-21 07:10

3 楼

你给这个link的solution太长了
好的解法十行上下就解决问题了
http://stackoverflow.com/questions/3208955/skyline-algorithm

【在 j****y 的大作中提到】

: http://elementsofprogramminginterviews.com/solutions/
: search "draw the skyline"

y*82014-10-21 07:10

4 楼

谢谢指点！

【在 j****y 的大作中提到】

: http://elementsofprogramminginterviews.com/solutions/
: search "draw the skyline"

y*82014-10-21 07:10

5 楼

谢谢指点！

【在 l*****a 的大作中提到】

: 你给这个link的solution太长了
: 好的解法十行上下就解决问题了
: http://stackoverflow.com/questions/3208955/skyline-algorithm

x*w2014-10-21 07:10

6 楼

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.SortedSet;
import java.util.TreeSet;
public class EPI_15_1 {
static class Rect {
public int lft;
public int rgt;
public int height;

public Rect(int l, int r, int h) {
lft = l;
rgt = r;
height = h;
}
}

static class Point {
public boolean start;
public int pos;
public int height;

public Point(boolean s, int p, int h) {
start = s;
pos = p;
height = h;
}
}

static class PointComparator implements Comparator {
@Override
public int compare(Point o1, Point o2) {
return o1.height - o2.height;
}
}

static void printSkyLine(Rect[] rects) {
if (null == rects)
return;

Map map = new HashMap();
List points = new ArrayList();
for (Rect rect : rects)
{
Point s = new Point(true, rect.lft, rect.height);
Point e = new Point(false, rect.rgt, rect.height);
points.add(s);
points.add(e);
map.put(e, s);
}

Collections.sort(points, new Comparator() {
@Override
public int compare(Point o1, Point o2) {
return o1.pos - o2.pos;
}
});

SortedSet tree = new TreeSet(new PointComparator());
for (Point pt : points) {
int curHeight = tree.isEmpty() ? 0 : tree.last().height;
if (pt.start)
tree.add(pt);
else
tree.remove(map.get(pt));

if (tree.isEmpty())
System.out.println(pt.pos + " ===> " + curHeight);
else if (tree.last().height != curHeight)
System.out.println(pt.pos + " ===> " + tree.last().height);
}
}

public static void main(String[] strs) {
Rect[] rects = new Rect[8];
rects[0] = new Rect(0, 2, 1);
rects[1] = new Rect(1, 5, 3);
rects[2] = new Rect(3, 7, 4);
rects[3] = new Rect(4, 8, 2);
rects[4] = new Rect(6, 13, 3);
rects[5] = new Rect(9, 11, 5);
rects[6] = new Rect(10, 15, 1);
rects[7] = new Rect(12, 14, 2);

printSkyLine(rects);
}

}

a*l2014-10-21 07:10

7 楼

我觉得只需要一个max heap获取维护当前最高顶, 和一个点集来保存skyline的边界点。
先把所有坐标按x轴排序（无论起点还是终点），然后从左到右扫描：
每扫到一个起点S，就把当前楼顶L加入heap，如果L是最高顶时，skyline中添加起点S
，以及S和之前最高顶的交点；
每扫到一个终点E，如果当前楼顶L不是heap中最高顶，忽略；如果是最高顶，从heap中
删除L，然后在heap中找到现存的最高顶L1（从heap中不断取出最高顶如果是之前终结
的就继续直到heap为空，此时L1为地平线），然后skyline中要添加当前终点E，以及E
和L1的交点。
时间复杂度为O(nlogn)，空间复杂度为O(n)。

b*a2014-10-21 07:10

8 楼

The algorithm in your link is not efficient because it needs too much space
if the intervals span a long range. On the other hand, the implementation
in EPI is best in my opinion.

【在 l*****a 的大作中提到】

: 你给这个link的solution太长了
: 好的解法十行上下就解决问题了
: http://stackoverflow.com/questions/3208955/skyline-algorithm

y*82014-10-21 07:10

9 楼

我觉得他说的答案是这个：http://www.algorithmist.com/index.php/UVa_105
Sweep Line 应该是正解。
按照begin排序入heap，按照end顺序出heap，同时用Red-Black-Tree保持当前最高高度
。总体复杂度O(NlogN).

space

【在 b*****a 的大作中提到】

: The algorithm in your link is not efficient because it needs too much space
: if the intervals span a long range. On the other hand, the implementation
: in EPI is best in my opinion.