646最长数对链

柔光的暖阳◎ 2023-02-25 07:22 11阅读 0赞

## 一、前言 ##

分类：动态规划。

问题来源LeetCode 646 难度：中等。

问题链接：[https://leetcode-cn.com/problems/maximum-length-of-pair-chain][https_leetcode-cn.com_problems_maximum-length-of-pair-chain]

## 二、题目 ##

给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。给定一个对数集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

**示例1：**

输入: \[\[1,2\], \[2,3\], \[3,4\]\] 输出: 2 解释: 最长的数对链是 \[1,2\] -> \[3,4\]

**注意：**

1.  给出数对的个数在 \[1, 1000\] 范围内。

## 三、思路 ##

和[《300最长上升子序列》][300]很类似，但没有对数对相对位置有要求。先对数对进行排序，如果从头扫描一次就可以了，相比[《300最长上升子序列》][300]这道题更简单，需要注意的是数对排序规则和比较判断。

## 四、编码实现 ##

//==========================================================================
    /*
    * @file    : 646_FindLongestChainh.h
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/107274137
    * @author  : niebingyu
    * @date    : 2020/07/10
    * @title   : 646.最长数对链
    * @purpose : 给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
    * 现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
    * 给定一个对数集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
    *
    * 示例 1：
    * 输入: [[1,2], [2,3], [3,4]]
    * 输出: 2
    * 解释: 最长的数对链是 [1,2] -> [3,4]
    *
    * 注意：
    * 给出数对的个数在 [1, 1000] 范围内。
    *
    *
    * 来源：力扣（LeetCode）
    * 难度：中等
    * 链接：https://leetcode-cn.com/problems/maximum-length-of-pair-chain
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    #define NAMESPACE_FINDLONGESTCHAINH namespace NAME_FINDLONGESTCHAINH {
    #define NAMESPACE_FINDLONGESTCHAINHEND }
    NAMESPACE_FINDLONGESTCHAINH
    
    class Solution
    {
    public:
    	int findLongestChain(vector<vector<int>>& pairs)
        {
            int len = (int)pairs.size();
            if (len == 0) return 0;
            sort(pairs.begin(), pairs.end(), [](const vector<int>& a, const vector<int>& b) 
                { return (a[0] == b[0] && a[1] < b[1]) || (a[0] < b[0]); });
    
            vector<int> t = pairs[0];
            int maxLen = 1;
            for(int i = 1;i < len;i++)
            {
                if (pairs[i][0] > t[1])
                {
                    t = pairs[i];
                    ++maxLen;
                }
                else if (pairs[i][0] > t[0] && pairs[i][1] < t[1])
                {
                    t = pairs[i];
                }
            }
    
             return maxLen;
        }
    };
    
    
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, vector<vector<int>>& pairs, int expect)
    {
        Solution s;
        int result = s.findLongestChain(pairs);
        if (expect == result)
            cout << testName << ", solution passed." << endl;
        else
            cout << testName << ", solution failed. expect:" << expect << ", result:" <<result << endl;
    }
    
    // 测试用例
    void Test1()
    {
        vector<vector<int>> pairs =
        {
            {1,2},
            {2,3},
            {3,4}
        };
        int expect = 2;
        test("Test1()", pairs, expect);
    }
    
    void Test2()
    {
        vector<vector<int>> pairs =
        {
            {3,4},
            {2,3},
            {1,2}
        };
        int expect = 2;
        test("Test2()", pairs, expect);
    }
    
    void Test3()
    {
        vector<vector<int>> pairs =
        {
            {-10, -8},
            {8, 9},
            {-5, 0},
            {6, 10},
            {-6, -4},
            {1, 7},
            {9, 10},
            {-4, 7}
        };
        int expect = 4;
        test("Test3()", pairs, expect);
    }
    NAMESPACE_FINDLONGESTCHAINHEND
    // 测试 用例 END
    //
    
    void FindLongestChainh_Test()
    {
        NAME_FINDLONGESTCHAINH::Test1();
        NAME_FINDLONGESTCHAINH::Test2();
        NAME_FINDLONGESTCHAINH::Test3();
    }

[https_leetcode-cn.com_problems_maximum-length-of-pair-chain]: https://leetcode-cn.com/problems/maximum-length-of-pair-chain
[300]: https://blog.csdn.net/nie2314550441/article/details/107269090