[leetcode] 646. Maximum Length of Pair Chain

[leetcode] 646. Maximum Length of Pair Chain

Description

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: 2Explanation: The longest chain is [1,2] -> [3,4]

Note:

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

分析

题目的意思是：找出链对的最大长度。

dp[i]代表前i个pair能够组成链对的最大长度。首先是按照链对的第二个值从小到大排序。如果当前链对的第一个值大于一个数的第二个值，则更新：dp[i]=max(dp[i],dp[j]+1)， 取最大长度。最后遍历dp数组得到最大值即为所求。

代码

class Solution {public: int findLongestChain(vector>& pairs) { sort(pairs.begin(),pairs.end(),[](vector&a,vector&b){ return a[1] dp(n,1); for(int i=1;ipairs[j][1]){ dp[i]=max(dp[i],dp[j]+1); } } } int ans=0; for(int i=0;i

参考文献

​​[LeetCode] Maximum Length of Pair Chain 链对的最大长度​​​​646. Maximum Length of Pair Chain​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。