algorithm - 最长的对链

Question

You are given n pairs of numbers. In every pair, the first number is always smaller than the second number. A pair (c,d) can follow (a,b) if and only if b is less than c. Chains of pairs can be formed in this manner. Find the longest chain of pairs formed.

我在接受亚马逊采访时遇到了这个问题，但找不到答案，只是它与 LIS problem 有关。 .

Answer 1

因为每个 (X,Y) 对的两个值必须按顺序 (X < Y)，并且一对的 Y 值必须小于下一对的 X 值，所以你实际上是在构建一个连续的沿着一个维度的值(value)链。 您只需按 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值不够高，以后还会如此。