leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0646.cpp (854B)

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 };