【leetcode】【2022/9/3】646. 最长数对链

问题描述：

• 给出 n 个数对，在每一个数对中，第一个数字总是比第二个数字小。
  • 现在定义一种跟随关系，当且仅当 b < c 时，数对 (c, d) 才可以跟在 (a, b) 后面，用这种形式来构造一个数对链。
• 给定一个数对集合，找出能够形成的最长数对链的长度。【不需要用到所有的数对，可以以任何顺序选择其中的一些数对来构造】

核心思路：

• 可以把数对看作时间，即该题就是找出尽量多不重叠的时间区间。
• 一种方法是排序 + 动态规划。
  • 创建一维 dp 数组，其中 dp[i] 代表以数对 pairs[i] 为结尾的最长数对链长度。
  • 该解法其实是暴力求解，排序后遍历数组，在当前数对 pairs[i] 下搜索所有索引小于 i 的数对 pairs[j]，判断 paris[i][0] 是否大于 paris[j][1]，如果大于，则说明区间不重叠，此时 dp[i] = max(dp[i], dp[j] + 1)。
• 另一种方法是排序 + 贪心。
  • 贪心策略其实就是想明白如何作出局部最优。
  • 在区间问题上，为了找出更多不重叠的区间，最好的策略就是选择最先结束的，最先结束的不会影响后续的区间数。
  • 因此假设数对为 [start, end]，就先将 pairs 数组按照 end 来排序。
  • 排序后不断将先结束的并且和前面不重叠的数对加入链中即可。

代码实现：

• 动态规划解法代码实现如下：

  class Solution
  {
  public:
      int findLongestChain(vector<vector<int>>& pairs)
      {
          int m = pairs.size();
          vector<int> ans(m, 1);
          sort(pairs.begin(), pairs.end());
          for(int i = 1; i < m; ++i)
          for(int j = i-1; j >= 0; --j)
          {
              if(pairs[i][0] > pairs[j][1])
                  ans[i] = max(ans[i], ans[j]+1);
          }
          return ans[m-1];
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

• 贪心解法代码实现如下：

  class Solution
  {
  public:
      int findLongestChain(vector<vector<int>>& pairs)
      {
          sort(pairs.begin(), pairs.end(), [&](const vector<int>& a, const vector<int>& b)
          {
              return a[1] < b[1];
          });
          int cnt = 1, pre = pairs[0][1];
          for(int i = 1; i < pairs.size(); ++i)
          {
              if(pairs[i][0] > pre)
              {
                  ++cnt;
                  pre = pairs[i][1];
              }
          }
          return cnt;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21