leetcode

0 // DP, O(n^2)

1 class Solution {

2 public:

3 int findLongestChain(vector<vector<int>> &pairs) {

4 sort(begin(pairs), end(pairs));

5 const int n = pairs.size();

6 int res = 1, count[1001] = {0};

7 for (int i = n - 1; i >= 0; i--) {

8 for (int j = i + 1; j < n; j++) {

9 if (pairs[i][1] < pairs[j][0]) count[i] = max(count[i], count[j]);

10 }

11 res = max(res, ++count[i]);

12 }

13

14 return res;

15 }

16 };

17

18 // Greedy, O(nlogn)

19 class Solution {

20 public:

21 int findLongestChain(vector<vector<int>> &pairs) {

22 sort(pairs.begin(), pairs.end(), [](const auto &a, const auto &b) { return a[1] < b[1]; });

23

24 int curr = INT_MIN, ans = 0;

25 for (const auto &pair : pairs) {

26 if (pair[0] > curr) curr = pair[1], ans++;

27 }

28 return ans;

29 }

30 };