algorithm - 扫描线算法 - 一维平面的实现

Question

问题很简单，平面上有一些给定的一维直线。我们需要找到至少有一行的空间的总大小。

让我用一个示例图像来讨论这个问题-

这可能是个案。或者

这可能是一个案例或类似的事情。

我知道这是Sweep Line Algorithm的一个基本问题.

但是网上没有合适的文档可以让它正确理解。

我拥有的最好的一个是 Top Coder 的博客，即 here .

但目前尚不清楚如何实现它或如何模拟。

如果我愿意，我们可以用 2 个循环在 O(n^2) 中完成它，但我不知道该过程是怎样的。

或者有比 O(n log n) 更好的算法吗？

任何人都可以通过分享任何 Sudo 代码或模拟来帮助我吗？

如果 Sudo 代码或示例代码不可用，从我可以实现的地方进行理解模拟就足够了。

---

Re- Problem calculating overlapping date ranges不是我想要的，因为首先，它是 O(n^2)，所以，这不是我想要的。并且没有像这个问题那样完整描述。

Answer 1

没有太多关于此主题的信息。

所以，我正在与您分享我为您创建的算法和模拟，它也是 O(n log n) !!!!!

让我们开始吧

1. 创建所有行动点的优先列表(行动点是一条线的起点或终点)。 PQ 的每一项都有 3 个元素(当前点、开始或结束、来自哪一行)。 (O(n log n) 操作，如果我们使用 Quick Short 进行排序。
2. 初始化用于存储当前事件行的 Vector。
3. 初始化一个数组，大小 = 行数 + 1(用于存储影子长度之和)。

1. 现在从 PQ 中删除一个项目并为该项目运行特定操作，如下图所示，您就完成了。

0

1

2

3

4

5

6

7

8

9

10

11

1. 一直这样做直到 PQ 为空。

在你的例子中，找到数组从 1 到末尾(索引号 1 到 m)的所有元素的总和，这就是你的答案。

但是使用这个算法和数组，你可以很容易地得到许多更复杂的问题答案，比如有 3 个影子的空间的长度是多少 = Arr 3等等。

现在的问题是什么是秩序，对吧？

因此，排序 = O(n log n)和清扫 = O(m) [m=行动点数，所以 m

因此，总阶数 = O(n log n) + O(m) = O(n log n)

认为您可以轻松理解它，这将对您和其他许多人有很大帮助。并认为您将能够轻松实现它。