Classical DP solution by C++


  • 0
    S
    class Solution {
    public:
        int findLongestChain(vector<vector<int>>& pairs) {
            auto comp=[](const vector<int>& p1,const vector<int>& p2) {
                return p1[1]<p2[1]||(p1[1]==p2[1]&&p1[0]<p2[0]);
            };
            sort(pairs.begin(),pairs.end(),comp);
            int s=pairs.size();
            if(s==0) {return 0;}
            if(s==1) {return 1;}
            vector<int> dp(s);
            int i,j;
            dp[0]=1;
            int res=1;
            for(i=1;i<s;i++) {
                dp[i]=1;
                int tt=0;
                for(j=0;j<=i;j++) {
                    if(pairs[i][0]>pairs[j][1] && tt<dp[j]) {
                        tt=dp[j];
                    }
                }
                dp[i]=tt+1;
                if(dp[i]>res) {res=dp[i];}
            }
            return res;
        }
    };
    

Log in to reply
 

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