# [C++] Clean Code

1. sort the pairs by their end in increasing order;
2. at any point, choose the pair that start after the tail end, then use it as the new tail;
``````class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), cmp);
int cnt = 0;
vector<int>& pair = pairs[0];
for (int i = 0; i < pairs.size(); i++) {
if (i == 0 || pairs[i][0] > pair[1]) {
pair = pairs[i];
cnt++;
}
}
return cnt;
}

private:
static bool cmp(vector<int>& a, vector<int>&b) {
return a[1] < b[1] || a[1] == b[1] && a[0] < b[0];
}
};
``````

In fact the comparator does not even need to compare the begin:

``````class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), cmp);
int cnt = 0;
for (int i = 0, j = 0; j < pairs.size(); j++) {
if (j == 0 || pairs[i][1] < pairs[j][0]) {
cnt++;
i = j;
}
}
return cnt;
}

private:
static bool cmp(vector<int>& a, vector<int>&b) {
return a[1] < b[1];
}
};
``````

• Why does the longest chain always start with the first one in the sorted pairs? I am confused about it.

• @Wanhui because you always want to use the pair that end the earlier the better, so that you have more flexibility to use any other pair.

• @alexander
This solution is more clear and better in time complexity, especially comcompared to the current top rated answer "easy dp".
This one might take O(NlogN) + O(N), while "easy dp" takes O(nlogn) + O(N^2)

Maybe this is any problem or drawback which havn't identified?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.