leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0646.cpp (854B)

      1 // DP, O(n^2)
      2 class Solution {
      3   public:
      4     int findLongestChain(vector<vector<int>> &pairs) {
      5         sort(begin(pairs), end(pairs));
      6         const int n = pairs.size();
      7         int res = 1, count[1001] = {0};
      8         for (int i = n - 1; i >= 0; i--) {
      9             for (int j = i + 1; j < n; j++) {
     10                 if (pairs[i][1] < pairs[j][0]) count[i] = max(count[i], count[j]);
     11             }
     12             res = max(res, ++count[i]);
     13         }
     14 
     15         return res;
     16     }
     17 };
     18 
     19 // Greedy, O(nlogn)
     20 class Solution {
     21   public:
     22     int findLongestChain(vector<vector<int>> &pairs) {
     23         sort(pairs.begin(), pairs.end(), [](const auto &a, const auto &b) { return a[1] < b[1]; });
     24 
     25         int curr = INT_MIN, ans = 0;
     26         for (const auto &pair : pairs) {
     27             if (pair[0] > curr) curr = pair[1], ans++;
     28         }
     29         return ans;
     30     }
     31 };