最小边交点算法

Question

(在有人问之前，这不是作业。)

假设您有 2 个数组 y0 和 y1，其中

y0 = [1,2,3,4,5,6] 和y1 = [2,1,6,3,4,5]

注意 y0[0] = y1[1] = 1，它本质上意味着 y0[0] 连接到 y1[1]。类似地，y0[2] = y1[3] = 3 所以它们也是“连接”的。

(图片由 belisarius 提供)

一个数组中的每个元素在第二个数组中都有对应的条目。 将数组中的每个元素想象成一​​个顶点，并将这些连接想象成从一个数组到另一个数组的边。

我需要找到一组边(最大尺寸)，这样所有“边”(或线)都不会相交。

在上面的例子中，注意，

1. Edge 1 和 Edge 2 将相交。
2. Edge 6 将与 Edge 3、Edge 4、Edge 5 相交。

因此，解决方案可以是 1,3,4,5 或 2,3,4,5(大小 = 4)，因为这些行都不会彼此相交。可以有多种解决方案，但我只需要一个。

我的问题，是否有任何已知的 CS 问题与此类似？我应该使用什么算法？

我已经尝试用一个例子来解释我的问题，但是，如果仍然不清楚，我会澄清任何疑问。提前致谢。

Answer 1

假设单个数组中没有元素重复，这就是最长递增子序列。

不失一般性，假设第一个数组 A1 恰好是 [1, 2, 3, ..., n] .这种转换可以在 O(n) 的哈希集或 O(nlogn) 的 BST 中完成。

请注意，当且仅当它包含 i 时，我们的集合才有交叉点和 j与 i < j但是j出现在 i 之前在第二个数组 A2 中(我们知道自 i < j 以来 i 出现在 A1 中的 j 之前)。

那么如果一个集合没有交叉，它显然对应于 A2 的递增子序列，反之亦然。

最长递增子序列有一个简单的 O(n^2) 解和一个稍微复杂的 O(nlogn) 解。