最小边交点算法

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之前出现j在A1).

然后,如果一组没有交叉,则它明显对应于A2的增加的子序列,反之亦然.

最长的子序列具有简单的O(n ^ 2)解和稍微复杂的O(nlogn)解.