20CN网络安全小组论坛 - 编程破解 - 关于著名的SKYLINE问题

论坛: 编程破解标题: 关于著名的SKYLINE问题

复制本贴地址

作者: akami3rd [akami3rd]

论坛用户

不是什么黑客题目，正规竞赛题，请教各位大虾。会的人请给个algorithm。 http://acm.uva.es/problemset/v1/105.html

地主发表时间: 04-11-06 11:01

回复: hannyu [hannyu]

论坛用户

嘿嘿，谢谢
这个望站不错。
此算法我觉得可以有两个思路
思路一：
1，对整个（L，H，R）集合做快排成按H递减的顺序；
2，需要附设一个链表A，对排好序的集合从第1个元素开始，以此元素的（L，R）为一个结点插入链表A，若不能插入（即插入点在某个结点的L，R之间或包含某结点）则删除多余部分再插，具体该怎么办就怎么办
3，最后输出该链表即为答案
缺点：时间复杂度和空间复杂度都高
优点：不失为一个algorithm

思路二：
1，按L递增来排序列
2，顺序遍历，MAX纪录最高点，……后面的不用说了吧。
3，输出
缺点：说起来简单做起来难，关键是第二步需要一些技巧
优点：比思路一好

不要叫我写具体的，TIME IS MONEY！何况我还要考研！
因为从来没写过这样的算法，肯定很肤浅，希望高手来指点！

B1层发表时间: 04-11-07 17:47

回复: akami3rd [akami3rd]

论坛用户

谢谢 hanyu 。我会尝试第二个。同时募集其他有高论。

B2层发表时间: 04-11-07 18:37

论坛: 编程破解