为了增强如何使用最长的增长子序列算法来解决该问题的方法，让我们从一些直觉开始，然后构建一个解决方案。由于您只能在匹配索引的城市之间建立桥梁，因此可以将最终建立的桥梁集合视为可以找到的最大对，其中不包含任何交叉。那么在什么情况下您会过马路？

让我们看看何时会发生这种情况。假设我们对第一个城市建造的所有桥梁进行排序。如果有两个桥相交，那么我们必须有一个桥（a i，b i），使得对于其他一些桥（a
j，b j），下列条件之一成立：

• 一个我 <一个Ĵ和b 我 > b Ĵ
• a i > a j和b i <b j

第一种情况是说，有一座桥，其顶部城市比我们的桥的起点靠右，而其底部城市比我们的桥的终点靠左，而第二种情况则处理相反的情况。

鉴于需要保留此属性，因此我们需要确保对于每组桥，对于任何一对桥（a i，b i），（a j，b j），我们都具有以下两个属性之一。：要么

• 一个我 ≤一个Ĵ和b 我 ≤b Ĵ

要么

• 一个我 ≥一个Ĵ和b 我 ≥b Ĵ

换句话说，如果我们要按桥的第一个坐标对它们进行排序，则第二个坐标的集合将一直在增加。同样，如果我们要按桥的第二坐标对桥进行排序，则第一坐标将一直在增加。

我们刚刚定义的定义偏序≤酒店都在集桥梁，在这里我们说（一个我，B 我）≤ 两个（一个Ĵ，B Ĵ）如果我 ≤一Ĵ和b 我 ≤ b Ĵ。请注意，这不是总排序-
例如，（1，2）与（2，1）无法比拟-但这是部分排序，因为它是自反的，反对称的和可传递的。

鉴于此，问题的目标是找到可以通过这种关系完全排序的最大元素集，因为如果我们有一个包含两个不可比元素的集，则这些元素必须代表跨桥。换句话说，我们希望以偏序找到最长的链。一种实现方法是，在O（n
2）时间内将每个元素相互比较，并查看哪些元素可以按≤ 两个进行排序。这将产生一个有向无环图，其中（a i，b i）对具有（a j，b j）iff（a i，b
i）≤ 两者（a
j，bj）。一旦我们有了这个向无环图，我们可以再找出最长路径图中的发现最大的一组是调用由≤比较的元素的两个，然后给出了解决问题的办法。因此，总运行时间为O（n
2）。

但是，我们可以做得更好。上述算法的问题在于，我们无法轻易分辨出元素之间的比较方式，因此我们必须明确地将每个城市与另一个城市进行比较。

2  5  8 10
6  4  1  2

让我们按底行对城市进行排序：

8 10  5  2
1  2  4  6

现在，这是非常酷的观察。如果我们具备的要素排序由他们的底行，那么我们可以说，如果两对通过订购≤
都通过查看他们在第一行中的位置。如果第一对在第二对的左边，我们立即知道第一对的第二个元素小于第二对的第二个元素，因为我们已经按第二个坐标对它们进行了排序。然后，如果第一对中的第一个元素小于第二对中的第一个元素，则可以将这对元素一起构建。因此，如果我们想找到一组可以一起建造的桥，我们正在寻找最上面一行的子序列，因为在这种情况下，当我们从中间移开时，对中的第一和第二个元素都在增加。从左到右。找到最长的增长子序列即可解决此问题。

ew！希望这个答案能详细解释一切！