README.md

646. Maximum Length of Pair Chain (Medium)

You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.

Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.

Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.

Example 1:

Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]

Note:

1. The number of given pairs will be in the range [1, 1000].

Related Topics:
Dynamic Programming

Similar Questions:

• Longest Increasing Subsequence (Medium)
• Increasing Subsequences (Medium)

Solution 1. DP

First sort the array in ascending order.

Let dp[i] be the length of maximum chain formed using a subsequence of A[0..i] where A[i] must be used.

dp[i] = max(1, max(1 + dp[j] | pair j can go after pair i ))

// OJ: https://leetcode.com/problems/maximum-length-of-pair-chain/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
    int findLongestChain(vector<vector<int>>& A) {
        sort(begin(A), end(A));
        int N = A.size();
        vector<int> dp(N, 1);
        for (int i = 1; i < N; ++i) {
            for (int j = 0; j < i; ++j) {
                if (A[j][1] >= A[i][0]) continue;
                dp[i] = max(dp[i], 1 + dp[j]);
            }
        }
        return *max_element(begin(dp), end(dp));
    }
};

Solution 3. Interval Scheduling Maximization (ISM)

// OJ: https://leetcode.com/problems/maximum-length-of-pair-chain/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int findLongestChain(vector<vector<int>>& A) {
        sort(begin(A), end(A), [](auto &a, auto &b) { return a[1] < b[1]; });
        int e = INT_MIN, ans = 0;
        for (auto &v : A) {
            if (e >= v[0]) continue;
            e = v[1];
            ++ans;
        }
        return ans;
    }
};