646. 最长数对链

题号：646
来源：LeetCode
难度：中等
标签：dp 排序
语言：TypeScript
解法：1 个
作者：lmliheng
最近更新：2026-09-27

TypeScript · O(n^2) 时间 · O(n) 空间 · 更新于 2026-09-27

按左端点排序后做LIS式DP

typescript

/**
 * @difficulty medium
 * @tags dp,排序
 * @time O(n^2)
 * @space O(n)
 * @note 按左端点排序后做LIS式DP
 * @646. 最长数对链
 */
/**
 * 最长数对链
 */
let pairs = [[1, 2], [2, 3], [3, 4]]
let res = 0
let n = pairs.length
pairs.sort((a, b) => a[0] - b[0])
let dp = new Array(n).fill(1)
for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
        if (pairs[i][0] > pairs[j][1]) {
            dp[i] = Math.max(dp[i], dp[j] + 1)
        }
    }
}

console.log(dp)

源码：ts/leetcode/646. 最长数对链.ts

在 GitHub 上查看题目所在目录：lmliheng/algorithm

646. 最长数对链 ​

646. 最长数对链