My c++ solution by using dp


  • 0
    X

    using dp can slove the problem easily!

    1. sort
    2. the res[i] is max(res[0] ,res[1]...res[i - 1]) + 1
    class Solution {
    public:
        static bool cmp(vector<int>& a, vector<int>& b)
        {
            if(a[0] != b[0])
                return a[0] < b[0];
            else
                return a[1] < b[1];
        }
        
        int findLongestChain(vector<vector<int>>& pairs) {
            int len = pairs.size();
            if(!len) return 0;
            sort(pairs.begin(),pairs.end(),cmp);
            vector<int> res(len,1);
            
            for(int i = 0; i < len; i++)
            {
                for(int j = i - 1; j >= 0; j--)
                {
                    if(pairs[j][1] < pairs[i][0])
                    {
                        res[i] += res[j];
                        break;
                    }
                }
            }
            return res[len - 1];
        }
    };
    

Log in to reply
 

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