给定 n 对数字,第一个数字总是小于第二个数字。当且仅当 b <= c 时,一对 (c, d) 可以跟随一对 (a, b)。可以以这种方式形成对链。找出可以由一组给定的对组成的最长链。
例如{ (1,2), (3,4), (5,7), (9,10), (7,9), (8,9), (0,6) }
所以输出应该是:{(1,2), (3,4), (5,7), (8,9), (9,10)}
我的算法如下:
1. Sort the list according to the 2nd number of elements
i.e.`{ (1,2), (3,4), (0,6), (5,7), (7,9), (8,9), (9,10) }`
2. choose the first element from the list i.e. `(1,2)`
3. for each element e in the list left
4. choose this element e if the first number of the element is greater than the 2nd number of the previous element. i.e. after `(1,2)` choose `(3,4)` because `3 > 2.`
在上述算法之后,您将获得输出为{(1,2), (3,4), (5,7), (8,9), (9,10)}
.
请让我知道算法的正确性。谢谢。
编辑:
更直观的正确性证明:
证明:在链中包含更多对的唯一方法是将一对替换为 Y 值较小的一对,以允许下一对具有较小的 X 值,从而可能适合之前无法适合的另一对。如果您将一对替换为具有相同 Y 值的一对,您将一无所获。如果替换具有较大的 Y 值,那么您所做的只是可能阻止一些以前适合的对。
因为这些对已按 Y 值排序,所以您永远不会找到具有较小 Y 的替代品。在排序的对中“向前”看,它们都将具有相同或更大的 Y 值。“向后看”,最初从链中淘汰的任何东西都是因为 X 值不够高,情况仍然如此。
这是取自这里