algorithm - 最长链对

Question

你会得到n一对数字。在每一对中，第一个数字总是小于第二个数字。当且仅当小于时，一对(c,d)可以跟随。可以以这种方式形成对链。找到形成的最长链对。(a,b)bc

我在接受亚马逊采访时得到了这个问题，但无法弄清楚答案，只是它与LIS 问题有关。

Answer 1

因为每个 (X,Y) 对的两个值必须按顺序 (X < Y)，并且一对的 Y 值必须小于下一对的 X 值，所以您实际上是在构建一个连续的值链沿着一个维度。您只需要按 Y 值排序。

鉴于此示例数据：

(15,40) (5,8) (1,10) (6,8) (9,20) (2,4) (36,37) (34,35) (9,14) (30,31)

按 Y 排序得到：

(2,4) (6,8) (5,8) (1,10) (9,14) (9,20) (30,31) (34,35) (36,37) (15,40)

然后循环遍历，如果 X 大于链中的最后一个 Y，则将其添加到链中，否则忽略它。

请注意，在此示例中，(6,8)恰好在(5,8). 当 Y 值相等时，为链选择哪一对并不重要，只要 X 值满足大于前一个 Y 的条件即可。

这是一个图表，将排序的对显示为数轴上方的条形。从第一对 开始，(2,4)添加到底部链中的每个都是黄色的。在视觉上，灰色的被跳过，因为有一个黄色的“阻碍”它被放入链中（重叠值）。

证明：在链中包含更多对的唯一方法是用 Y 值较小的一对替换一对，以允许下一对具有较小的 X 值，从而可能适合之前无法适合的另一对。如果您将一对替换为具有相同 Y 值的一对，您将一无所获。如果替换具有较大的 Y 值，那么您所做的只是可能阻止一些以前适合的对。

因为这些对已按 Y 值排序，所以您永远不会找到具有较小 Y 的替代品。在排序的对中“向前”看，它们都将具有相同或更大的 Y 值。“向后看”，最初从链中淘汰的任何东西都是因为 X 值不够高，情况仍然如此。

Answer 2

首先，这个问题可以看作是在二维网格上绘制点，其中每个点的 x 坐标小于该点的 y 坐标。现在你被要求找到最长的链，使得每个第 i+1 个点都在第 i 个点的上方和右侧（并且第 i 个点的 y 坐标小于 i+ 的 x 坐标第 1 点）。

现在让我们首先根据它们的 x 坐标对点进行排序。然后我们从最低的 x 坐标开始访问排序后的点，如果 x 坐标存在平局，那么我们将首先访问 y 坐标较高的点。现在举个例子，如果我们正在处理第 i 个点，我们知道所有已经访问过的点的 x 坐标都低于第 i 个点。因此，点 i 处的最长链末端将是我们已经获得的最长链，其中 y 坐标<= x 坐标为当前点。

我们可以使用有效的数据结构（如段树或二叉索引树）有效地完成此任务。

该解决方案的运行时间为：O(NlgN)，其中 N 是点数（给定问题中的对数）。

Answer 3

解决这个问题的一个基本方法是创建一棵树，其中每个节点都是一对，并在合法时构造从一个节点到另一个节点的有向边（即“一对 (c,d) 可以跟随 (a, b) 当且仅当 b 小于 c")。您可以从每个节点进行修改的广度优先遍历，以跟踪从该节点开始的最长路径的长度，当您完成时，只需查看所有节点以找到最长的路径。

Answer 4

我们可以从 Brian 的方法开始，即根据 y 值对所有对进行排序。它将确保上对的 X < 下对的 y 的要求条件。现在我们需要的是新的对列表中 x 的最长递增子序列。我们可以通过对所有 x 进行排序并找到排序后的 x 和先前创建的新列表之间的最长公共子序列来获得

Answer 5

在我看来，最长链的一个特征是它最小化任何两个相邻元组的总跨度（最大化任何范围内可能的元组数量）。

在这种情况下，正如 Brian Stephens 所建议的那样，我们只需要按第二个数字进行排序，升序（以保证搜索下一个元组时的最小跨度），并从排序列表中的第一个元组开始构建链。

我们可以通过假设如果 S(0) 是从第一个元组开始的链，则存在一个 S(i)，其中 i 不在 S(0) 中，它比 S(0) 长，我们可以证明这个解决方案是最优的); 因此还有一个比 S(1) 更长的链 S(i+1)。我们知道 i 的开始必须在 i-1 的结束之前，否则它会包含在 S(0) 中。现在如果 i-1 的结尾等于 i 的结尾，则 S(i+1) 将是 S(0) 的一部分，这与我们的前提相矛盾。或者，如果 i 的结尾大于 i-1 的结尾，则 S(i+1) 将再次包含在 S(0) 中。i 的结尾不能小于 i-1 的结尾，因为列表是按此属性排序的。