最长的一对链

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).只要X值满足大于先前Y的条件,当Y值相等时,为链选择哪一对并不重要.

这是一个图表,显示排序的对作为数字线上方的条形图.从第一对开始(2,4),每个添加到底部链的颜色为黄色.在视觉上,灰色的被跳过,因为它有一个黄色的"在路上"被放入链中(重叠的值).

证明:在链中包含更多对的唯一方法是用一个具有较小Y值的对替换一对,以允许下一对具有较小的X值,可能适合之前无法适合的另一对.如果用具有相同Y值的一对替换一对,则什么也得不到.如果替换具有更大的Y值,那么您所做的就是可能会阻挡一些之前适合的对.

因为这些对已按Y值排序,所以您永远不会找到具有较小Y的替换.在排序对中查找"向前",它们将具有相同或更大的Y值.看起来"向后",最初从链中消除的任何因素都是因为X值不够高,情况仍然如此.