leetcode 646. Maximum Length of Pair Chain 最长连续区间 + 排序 + 贪心算法

系统管理员 2022-06-03 06:47 30阅读 0赞

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\].

题意很简单，最直接的方法就是LISS最长递增子序列

规定了如果后面链对的首元素大于前链对的末元素，那么这两个链对就可以链起来，问我们最大能链多少个。那么我们想，由于规定了链对的首元素一定小于尾元素，我们需要比较的是某个链表的首元素和另一个链表的尾元素之间的关系，如果整个链对数组是无序的，那么就很麻烦，所以我们需要做的是首先对链对数组进行排序，按链对的尾元素进行排序，小的放前面。这样我们就可以利用**Greedy算法**进行求解了。

建议和[leetcode 300. Longest Increasing Subsequence 最长递增子序列LISS + 十分经典的动态规划DP做法][leetcode 300. Longest Increasing Subsequence _LISS _ _DP] 、[leetcode 368. Largest Divisible Subset 类似LISS最长递增子序列问题 + DP动态规划][leetcode 368. Largest Divisible Subset _LISS_ _ DP]和[leetcode 354. Russian Doll Envelopes 俄罗斯套娃 + 动态规划DP + 类似LISS最长递增子序列的做法][leetcode 354. Russian Doll Envelopes _ _ _DP _ _LISS]一起学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    using namespace std;
    
    bool cmp(vector<int>& a, vector<int>& b)
    {
        return a[1] < b[1];
    }
    
    class Solution
    {
    public:
        int findLongestChain(vector<vector<int>>& a) 
        {
            sort(a.begin(), a.end(), cmp);
            vector<vector<int>> all;
            all.push_back(a[0]);
    
            for (int i = 1; i < a.size(); i++)
            {
                if (all.back()[1] < a[i][0])
                {
                    all.push_back(a[i]);
                }
            }
            return all.size();
        }
    };

[leetcode 300. Longest Increasing Subsequence _LISS _ _DP]: http://blog.csdn.net/jackzhang_123/article/details/78122446
[leetcode 368. Largest Divisible Subset _LISS_ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/78173447
[leetcode 354. Russian Doll Envelopes _ _ _DP _ _LISS]: http://blog.csdn.net/jackzhang_123/article/details/78173297