646.最长数对链

链接：646.最长数对链
难度：Medium
标签：贪心、数组、动态规划、排序
简介：给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

题解 1 - cpp

• 编辑时间：2022-09-03
• 执行用时：32ms
• 内存消耗：2.2MB
• 编程语言：cpp
• 解法介绍：dp 记录当前点为结尾的最大链路。

impl Solution {
    pub fn find_longest_chain(pairs: Vec<Vec<i32>>) -> i32 {
        let mut pairs = pairs;
        pairs.sort_by(|a, b| {
            if a[0] != b[0] {
                a[0].cmp(&b[0])
            } else {
                a[1].cmp(&b[1])
            }
        });
        let len = pairs.len();
        let mut dp = vec![1; len];
        let mut ans = 0;
        for i in 0..len {
            for j in 0..i {
                if pairs[j][1] < pairs[i][0] {
                    dp[i] = dp[i].max(dp[j] + 1)
                }
            }
            ans = ans.max(dp[i]);
        }
        ans
    }
}