【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]; } }; - 贪心解法代码实现如下：
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; } };