m1:dp
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
auto func = [](vector<int>& a, vector<int>& b) { return a[1] < b[1]; };
std::sort(pairs.begin(), pairs.end(), func);
int n = pairs.size();
vector<int> dp(n, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (pairs[i][0] > pairs[j][1])
dp[i] = max(dp[i], dp[j] + 1);
}
}
return *max_element(dp.begin(), dp.end());
}
};
m2: 贪心
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
auto func = [](vector<int>& a, vector<int>& b) { return a[1] < b[1]; };
std::sort(pairs.begin(), pairs.end(), func);
int ret = 0;
int end = INT_MIN;
for (auto it : pairs) {
if (it[0] > end) {
ret++;
end = it[1];
}
}
return ret;
}
};
m3:贪心
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
auto func = [](vector<int>& a, vector<int>& b) { return a[1] < b[1]; };
std::sort(pairs.begin(), pairs.end(), func);
stack<vector<int>> s;
for (auto& it : pairs) {
if (s.empty()) s.push(it);
else
if (it[0] > s.top()[1]) s.push(it);
}
return s.size();
}
};