本文共 866 字，大约阅读时间需要 2 分钟。

1. 题目

给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个对数集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

示例 :输入: [[1,2], [2,3], [3,4]]输出: 2解释: 最长的数对链是 [1,2] -> [3,4]

来源：力扣（LeetCode）

2. 贪心解题

• 按照结束位置排序
• 与前面不相交，计数+1，更新结束位置为当前的结束位置

bool cmp(vector
   
     &a, vector
    
      &b){
   	return a[1] < b[1];}class Solution {
   public:    int findLongestChain(vector
     
      
       >& pairs) {
           sort(pairs.begin(), pairs.end(),cmp);        int count = 1, prevEnd = pairs[0][1];        for(int i = 1; i < pairs.size(); ++i)        {
           	if(pairs[i][0] > prevEnd)            {
                   ++count;                prevEnd = pairs[i][1];            }        }        return count;    }};
      
     
    
   

转载地址：https://michael.blog.csdn.net/article/details/101239559 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！