title
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]
solution
dp
class Solution {
public:
bool static cmp(vector<int> &a, vector<int>&b) {
return a[0] < b[0];
}
int findLongestChain(vector<vector<int>>& pairs) {
if (pairs.size() == 0) return 0;
sort(pairs.begin(), pairs.end(), cmp);
int n = pairs.size();
int ans = 1;
int *dp = new int[n + 1];
fill(dp, dp + n + 1, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (pairs[j][1] < pairs[i][0]) {
dp[i] = max(dp[i], dp[j] + 1);
ans = max(ans, dp[i]);
}
}
}
return ans;
}
};
按照第二个数字大小排序，然后确定最长数对链
class Solution:
def findLongestChain(self, pairs):
pairs.sort(key=lambda pair : pair[1])
length, last = 0, pairs[0][0]-1
for left, right in pairs:
if last < left:
length, last = length+1, right
return length