问题很简单，平面上有一些给定的一维线。
我们需要找到至少有一行的空间的总大小。
让我用一个示例图像来讨论这个问题 -
这可能是一个案例. Or
这可能是一个案例或类似的东西。
我知道这是一个基本问题扫线算法 https://en.wikipedia.org/wiki/Sweep_line_algorithm.
但互联网上没有合适的文档可以正确理解。
我最好的博客是顶级编码器那就是here https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/.
但目前尚不清楚如何实现它或如何进行模拟。
如果我愿意，我们可以用 2 个循环在 O(n^2) 内完成它，但我不知道这个过程是怎样的。
或者还有比 O(n log n) 更好的算法吗？
任何人都可以通过分享任何 Sudo 代码或模拟来帮助我吗？
如果 Sudo 代码或示例代码不可用，从我可以实现这一点的地方进行模拟以供理解就足够了。
Re- 计算重叠日期范围时出现问题 https://stackoverflow.com/questions/7468948/problem-calculating-overlapping-date-ranges不是我正在寻找的，因为首先，它是 O(n^2) 所以，这不是我想要的。而且没有像这个问题那样完全描述。
该主题没有太多可用信息。
所以，我正在与您分享我为您创建的算法和模拟，它也是O(n log n) !!!!!
开始吧-
- 创建所有操作点的优先级列表（操作点是一条线的起点或终点）。 PQ 的每一项都有 3 个元素（当前点、起点或终点、来自哪一行）。 (O(n log n)操作如果我们使用快速短线 https://en.wikipedia.org/wiki/Quicksort用于排序）。
- 初始化一个 Vector 来存储当前活动行。
- 初始化一个大小=行数+1的数组（用于存储阴影长度之和）。
- 现在从中删除一个项目PQ并对该项目运行特定操作，如下图所示，您就完成了。
1
2
3
4
5
6
7
8
9
10
11
- 一直这样做直到PQ为空。
在你的例子中，找到数组从 1 到结尾（索引 1 到 m）的所有元素的总和，这就是你的答案。
但是通过这个算法和数组，您可以轻松地得到许多更复杂的问题答案，例如具有 3 个影子的空间长度是多少 = Arr3 https://i.stack.imgur.com/10eWn.jpg等等。
现在的问题是订单怎么样, right?
所以，排序 = O(n log n)
扫掠 = O(m) [m=没有动作点，所以 m
因此，总阶数 = O(n log n) + O(m) =O(n log n)
认为您可以轻松理解它，并且将对您和其他许多人有很大的帮助。并认为您将能够轻松实现它。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
