algorithm - 找出非相交道路的最大间隔

Question

这是我一直试图解决的问题。

假设您有 2 条主干道 A 和 B，它们相互平行。现在我们有一组道路 R，它们都有一个端点在 A 上，另一个端点在 B 上。R 中的任何道路都不共享任何道路的端点。因此，如果 R 中有 r 条路，则有 2r 个不同的端点。除此之外，只要起点和终点在 A 和 B rados 处，这些道路可以延伸任意长度、斜向、平行或任意方向假设我们可以在 O(1) 时间内检查 2 条道路是否相交。

Q1) 找到 R 中道路的最大连续子集，其中没有两条不相交的道路相交。该算法应在 O(n log n) 内运行

Q2) 与 Q1 相同，但现在我们假设 2r 个不同的端点位于由 x² + y² = 1 给出的单位圆上

这个算法应该在 O(n³) 或更少的时间内运行。

到目前为止我的方法我尝试按 q1 的 2 个端点中的最小值对道路进行排序，以便我们的道路从最左边开始。然后我将遍历它们，并且仅检查其两个端点中的最小值是否在迭代道路的最小端点之后开始的道路，并削减这些道路并再次递归调用该函数。

但我不确定这是如何工作的。而且我不确定它是否为 O(n log n)

对于第 2 季度，我不知道。

我觉得这可以通过动态编程来完成，我缺少某种可以轻松解决这个问题的数据结构。请帮忙。

Answer 1

问题 1

您在道路 A 上有 N 个端点，在道路 B 上有 N 个端点。

根据第一个端点对 R 中的道路进行排序，并准备第二个端点的列表 A。

例如，如果我们有道路:

1->10
8->7
5->6

我们将按第一个端点将它们分类为:

1->10
5->6
8->7

并准备一个包含第二个端点的列表 A:

A = [10,6,7]

找到非重叠道路的最大子集等同于找到这个数组中最长的递增序列。

发现 longest increasing subsequence是具有 O(nlogn) 解的标准算法。

在这种情况下，最长的递增子序列是长度为 2 的 [6,7]，所以答案是 2。