对产业链最长 [英] Longest chain of pairs

问题描述

您给出 N 对数。在每对中，第一数总是比第二数目较小。一对（C，D）可以按照（A，B）当且仅当 b 小于 C 。可以以这种方式形成的双链。查找形成对的最长链。

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问题。

I got this question in an interview with Amazon but couldn't figure out the answer, just that it is related to the LIS problem.

推荐答案

由于每两个值（X，Y）的对必须在顺序（X LT，Y），以及一个对中的Y值必须小于比下一对的X值，你基本上是建立价值观的一个连续的链条沿着一个维度。 您只需要通过Y值进行排序。

Because the two values of each (X,Y) pair must be in order (X < Y), and the Y value of one pair must be less than the X value of the next pair, you are essentially building one continuous chain of values along one dimension. You just need to sort by the Y values.

鉴于这种样本数据：

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

排序用Y来获得：

Sort by Y to get:

(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值满足大于所述previous Y上条件

Notice that in this example, (6,8) happened to be sorted before (5,8). It doesn't matter which pair is chosen for the chain when their Y values are equal, as long as the X value satisfies the condition of being greater than the previous Y.

下面是显示了排序对，酒吧上面有一些线图。起始于第一对，（2,4），系统被加入到链上的底部的每一个被标记为黄色。从外观上看，灰色的是跳过，因为有一个黄色的在路上的它被投进链（重叠值）。

Here's a diagram showing the sorted pairs as bars above a number line. Starting at the first pair, (2,4), each one that is added to the chain at the bottom is colored yellow. Visually, the gray ones are skipped because there's a yellow one "in the way" of it being dropped into the chain (overlapping values).

证明： 以包括在链多对的唯一方法是用一个具有较小的Y值替换的一对，以允许下一对具有较小的X值，可能嵌合的另一对，其中它不能之前适合。如果你有一个具有相同的Y值替换一双，你一无所获。如果更换具有较大的Y值，你所做的一切是有可能阻止一些对将已经适应了。

Proof: The only way to include more pairs in the chain is to replace a pair with one with a smaller Y value, to allow for the next pair to have a smaller X value, potentially fitting another pair where it couldn't fit before. If you replace a pair with one with the same Y value, you gain nothing. If the replacement has a larger Y value, all you've done is potentially block some pairs that would've fit before.

由于对已被排序Y值，你永远不会找到一个替代以较小的Y.在排序对展望前进，它们将具有相同或更高的Y值。寻找向后，任何被从链条消除最初是因为X值不够高，这将仍然是这样。

Because the pairs have been sorted by Y values, you will never find a replacement with a smaller Y. Looking "forward" in the sorted pairs, they will all have the same or greater Y value. Looking "backward", any that were eliminated from the chain initially were because the X value wasn't high enough, which will still be the case.

这篇关于对产业链最长的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！