扫描线算法 - 一维平面的实现
Abr*_*hin 3 sorting algorithm simulation implementation mark-and-sweep
问题很简单,平面上有一些给定的1D线.我们需要找到至少有一行的空间总大小.
让我用一个示例图像讨论这个问题 -
这可能是一个案例.要么
这可能是一个案例或类似的事情.
我知道这是扫描线算法的基本问题.
但是互联网上没有适当的文件可以正确理解.
我最好的是Top Coder的博客,就在这里.
但目前尚不清楚如何实施它或如何进行模拟.
如果我想,我们可以在O(n ^ 2)中使用2个循环,但我无法实现程序如何.
或者是否有比O(n log n)更好的算法？
任何人都可以通过共享任何Sudo代码或模拟来帮助我吗？
如果Sudo代码或示例代码不可用,那么理解模拟就足以实现这一点.
计算重叠日期范围的重新问题不是我想要的,因为首先,它是O(n ^ 2),因此,它不是我想要的.并没有像这个问题那样完全描述.
这个主题没有太多可用的信息.
所以,我正在和你共享算法和模拟,由我为你创建,它也是O(n log n) !!!!!
开始吧-
- 创建所有动作点的优先级列表(动作点是一条线的起点或终点).PQ的每个项目都有3个元素(当前点,开始或结束,来自什么线).(如果我们使用Quick Short进行排序,则为O(n log n)操作).
- 初始化Vector以存储当前活动行.
- 初始化一个size = no of lines + 1的数组(用于存储阴影长度的总和).
- 现在从PQ中删除一个项目并运行该项目的特定操作,如下图所示,您就完成了.
0
1
2
3
4
五
6
7
8
9
10
11
- 并且在PQ为空之前执行此操作.
在你的情况下,找到数组的所有元素的总和从1到结尾(索引号1到m),这是你的答案.
但是使用这种算法和数组,您可以轻松地获得更复杂的问题答案,例如具有3 shadow = Arr 3的空间长度等等.
现在的问题是关于订单的问题,对吧？
因此,Sorting = O(n log n)和sweeping = O(m)[m =没有动作点,所以m
所以,总顺序是= O(n log n)+ O(m)= O(n log n)
认为您可以轻松理解它,并将为您和许多其他人提供很大的帮助.并且认为您将能够轻松实现它.