验证中...
私信发送成功
有一个数链,没个节点上有一对数字,计算没对数字可以相连的最大长度。
原始数据 复制代码
/*
问题:
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: The number of given pairs will be in the range [1, 1000].
*/
/*
解答:
要点:
1.一定要按照后一个数字进行排序,因为后一个数字的大小决定了下一对数字第一个数字的大小,也就决定了链的长度。
2.使用sort等泛型算法需要引用谓词时,如果谓词函数在类内,需要在函数定义时加static修饰符,同时函数传参要加
const 修饰符。
*/
#include<iostream>
#include<vector>
using namespace std;
class Solution
{
private:
static bool cmp(const vector<int> &a, const vector<int> &b)
{
return a[1] < b[1] || (a[1] == b[1] && a[0] < b[0]);
}
public:
int findLongestChain(vector< vector<int> >& pairs)
{
int i;
int cnt=0;
sort(pairs.begin(), pairs.end(), cmp);
vector<int> pre = pairs[0];
for(i=0; i<pairs.size(); i++)
if(i == 0 || pairs[i][0] > pre[1])
{
cnt++;
pre = pairs[i];
}
return cnt;
}
};
int main()
{
int i,j;
int m,n;
vector<int> q;
vector< vector<int> > p;
for(i=0; i<=2; i++)
{
cin>>m;
cin>>n;
q.push_back(m);
q.push_back(n);
p.push_back(q);
q.clear();
}
Solution sol;
cout<<sol.findLongestChain(p);
return 0;
}

评论列表( 0 )

你可以在登录后,对此项目发表评论