最长数对链 题目描述： 给定一个由数对组成的数组 pairs，其中 pairs[ i] = [ left_ i, right_ i]，且 left_ i < right_ i。我们定义数对 p2 = [ c, d] 可以跟在数对 p1 = [ a, b] 后面的条件是 b < c。这样形成的数对序列称为数对链。 请找出能够形成的最长数对链的长度。你不需要使用所有的数对，可以以任何顺序选择数对中的一部分来构造这个链。 示例： 输入: pairs = [ [ 1,2], [ 2,3], [ 3,4] ] 输出: 2 解释: 最长的数对链是 [ 1,2] -> [ 3,4]（注意，这里不能是 [ 1,2] -> [ 2,3]，因为 2 不小于 2，不满足 b < c 的条件） 解题过程： 步骤1：问题分析 这是一个典型的序列型动态规划问题，类似于最长递增子序列(LIS)，但元素是数对，连接条件是前一个数对的右边界严格小于后一个数对的左边界。我们需要找到一个最长的数对序列，使得每个数对都可以按顺序连接起来。 步骤2：状态定义 我们可以定义 dp[ i ] 表示以第 i 个数对作为结尾的最长数对链的长度。 步骤3：状态转移方程 对于每个数对 i，我们需要检查所有在它之前的数对 j（j < i），如果 pairs[ j][ 1] < pairs[ i][ 0 ]，那么数对 i 就可以接在数对 j 的后面，此时： dp[ i] = max(dp[ i], dp[ j ] + 1) 我们需要遍历所有 j < i，找到满足条件的最大值。 步骤4：初始条件 对于每个数对，至少可以单独形成一个长度为1的数对链，所以初始时所有 dp[ i ] = 1。 步骤5：计算顺序 为了确保在计算 dp[ i] 时，所有可能的 dp[ j]（j < i）都已经计算完成，我们需要按照一定的顺序遍历。这里我们可以先对数对进行排序，按照每个数对的第一个元素（左边界）升序排列，这样可以保证当我们处理第 i 个数对时，所有可能出现在它前面的数对都已经处理过。 步骤6：最终结果 最长数对链的长度就是 dp 数组中的最大值。 步骤7：详细推导过程 让我们通过一个具体例子来演示： 输入: pairs = [ [ 1,2], [ 2,3], [ 3,4] ] 先对数对按照第一个元素排序（已经是排好序的）： pairs = [ [ 1,2], [ 2,3], [ 3,4] ] 初始化 dp 数组：dp = [ 1, 1, 1 ] 计算每个位置的 dp 值： i = 0：第一个数对，前面没有数对，dp[ 0 ] = 1 i = 1：检查 j = 0 pairs[ 0][ 1] = 2, pairs[ 1][ 0 ] = 2 由于 2 < 2 不成立，所以不能连接 dp[ 1 ] = 1 i = 2：检查 j = 0 和 j = 1 j = 0：pairs[ 0][ 1] = 2 < pairs[ 2][ 0 ] = 3，成立 dp[ 2] = max(dp[ 2], dp[ 0 ] + 1) = max(1, 1+1) = 2 j = 1：pairs[ 1][ 1] = 3 < pairs[ 2][ 0 ] = 3，不成立 所以 dp[ 2 ] = 2 最终结果：max(dp) = max(1, 1, 2) = 2 步骤8：算法优化 我们可以进一步优化这个算法。观察发现，如果我们按照数对的右边界进行排序，而不是左边界，可以更高效地找到最长链。因为当我们按照右边界排序后，我们总是希望选择右边界最小的数对，这样可以为后面留下更多的选择空间。 贪心算法思路： 按照数对的右边界进行升序排序 初始化当前右边界为负无穷，链长度为0 遍历排序后的数对： 如果当前数对的左边界大于当前右边界，则可以将该数对加入链中，更新当前右边界为该数对的右边界，链长度加1 这种贪心方法的时间复杂度是 O(nlogn)，主要来自排序操作，比动态规划的 O(n²) 更高效。 步骤9：贪心算法验证 用同样的例子验证： pairs = [ [ 1,2], [ 2,3], [ 3,4] ] 按右边界排序后顺序不变 当前右边界 = -∞，链长度 = 0 处理 [ 1,2 ]：1 > -∞？是，加入链，当前右边界 = 2，链长度 = 1 处理 [ 2,3 ]：2 > 2？否，跳过 处理 [ 3,4 ]：3 > 2？是，加入链，当前右边界 = 4，链长度 = 2 结果与动态规划方法一致，但更加高效。 这个问题的关键在于理解数对链的连接条件，以及如何通过排序优化求解过程。两种方法都能正确解决问题，但贪心方法在效率上更优。