This is the 18th day of my participation in Gwen Challenge

The topic of dry

Let me give you n pairs. In every pair of numbers, the first number is always smaller than the second.

Now, we define a following relationship so that pairs (c, d) can follow (a, b) if and only if b < c. We construct a pair of numbers in this form.

Given a set of pairs, find the length of the longest chain of pairs that can be formed. You don’t need to use all the pairs, you can construct by selecting some of them in any order.

Example:

Input: [[1, 2], [2, 3], [3, 4]] output: 2: is the longest number of chain [1, 2] - > [3, 4]Copy the code

Solution: dynamic programming

This is actually the longest increment sequence problem.

In contrast, the sequences in this problem are out of order, and we have to sort them before we can find and record consecutive pairs. Then we compare the first digit of the first and the second digit of the second.

The determined recursive formula is:

 dp[i] = Math.max(dp[j] + 1,dp[i])
Copy the code

Notice that this is the maximum case for comparing the whole chain.

Code implementation:

Execution time: 208 ms, beating 20.59% of users in all JavaScript commits

Memory consumption: 45.9 MB, beating 13.23% of all JavaScript commits

/ * * *@param {number[][]} pairs
 * @return {number}* /
var findLongestChain = function (pairs) {
    pairs.sort((a,b) = >{
        return a[0]-b[0]})console.log(pairs)
    let len = pairs.length;
    if(len==1) return 1
    let dp = new Array(len).fill(1);
    dp[0] = 1;
    let maxNum=0;
    for (let i = 1; i < len; i++) {
        for (let j = 0; j < i; j++) {
            if (pairs[i][0] > pairs[j][1]) {
                dp[i] = Math.max(dp[j] + 1,dp[i])
            }
        }
        maxNum=Math.max(maxNum,dp[i])
    }
    return maxNum
};
Copy the code