# LeetCode Maximum Length of Pair Chain

LeetCode Maximum Length of Pair Chain
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].

bool cmp(const vector<int>& p1, const vector<int>& p2) {
return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]);
}
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), cmp);
int n = pairs.size();
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] = 0;
dp[0][1] = 1;
int ans = 1;
for (int i = 1; i < n; ++i) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = 1;
int j = i - 1;
while (j >= 0 && pairs[i][0] <= pairs[j][1]) {
--j;
}
if (j >= 0) {
dp[i][1] = max(dp[i][1], dp[j][1] + 1);
}
ans = max(ans, dp[i][0]);
ans = max(ans, dp[i][1]);
}
return ans;
}
};


class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), [](const vector<int>& p1, const vector<int>& p2) {return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]); });
int n = pairs.size(), ans = 1;
vector<int> dp(n, 1);
for (int i = 1; i < n; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (pairs[i][0] > pairs[j][1]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
}
return ans;
}
};


class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), [](const vector<int>& p1, const vector<int>& p2) {return p1[1] < p2[1]; });
int ans = 0;
for (int i = 0, j = 0; j < pairs.size(); ++j) {
if (j == 0 || pairs[j][0] > pairs[i][1]) {
++ans;
i = j;
}
}
return ans;
}
};


This site uses Akismet to reduce spam. Learn how your comment data is processed.