LeetCode 646 最长数对链[贪心 自定义排序] HERODING的LeetCode之路

解题思路：
从逆向思维角度出发，最后的最长数对链的第二个数一定是顺序排列的（当然第一个数也是顺序排列的），那么我们只需要按照第二个数的大小从小到大排序即可，这种情况可以保证第一个数绝对是最大贪心序列的第一个数，然后从中找子集，代码如下：

bool cmp(vector<int>& p1, vector<int>& p2) {
    return p1[1] < p2[1];
}

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