easy dp


  • 21
        public int findLongestChain(int[][] pairs) {
            if (pairs == null || pairs.length == 0) return 0;
            Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
            int[] dp = new int[pairs.length];
            Arrays.fill(dp, 1);
            for (int i = 0; i < dp.length; i++) {
                for (int j = 0; j < i; j++) {
                    dp[i] = Math.max(dp[i], pairs[i][0] > pairs[j][1]? dp[j] + 1 : dp[j]);
                }
            }
            return dp[pairs.length - 1];
        }
    

  • 0
    W

    @Yang_BU
    Very clear even for me, thanks


  • 2

    Same idea in python cannot get accepted.


  • 1
    H

    There is one problem called "Russian Doll Envelop" which used a binarysearch to optimize the double loop. Those two problem look similar to each other. Im wondering if that technique can be used here, as well. For now, I'm still thinking.


  • 0

    Yes. Definitely so. I solved this by using the binary search method.


  • 0
    S

    dp and greedy
    dp
    sort it with a[0] or a[1], in fact they are equal, then LIS

    class Solution {
    public:
        int findLongestChain(vector<vector<int>>& pairs) {
            
            int n = pairs.size();
            sort(pairs.begin(), pairs.end(), cmp);
            vector<int> dp(n,0);
            if(n==0)
                return 0;
            dp[0] = 1;
            int max_len = 1;
            for(int i=1;i<n;i++)
            {
                for(int j=0;j<i;j++)
                {
                    if(pairs[i][0]> pairs[j][1])
                        dp[i] = max(dp[i],dp[j]+1);
                }
                max_len = max(max_len,dp[i]);
            }
            return max_len;
        }
    private:
        static bool cmp(vector<int>& a, vector<int>& b)
        {
            return a[1] < b[1];
        }
            
    };
    

    greedy
    sort it with a[0]

    class Solution {
    public:
        int findLongestChain(vector<vector<int>>& pairs) {
            
            int n = pairs.size();
            sort(pairs.begin(), pairs.end(), cmp);
            int count  = 0;
            int cur_end = INT_MIN;
            for(int i=0;i<n;i++)
            {
                if(pairs[i][0] > cur_end)
                {
                    count ++;
                    cur_end = pairs[i][1];
                }
                   
                else if(pairs[i][1] < cur_end)
                    cur_end = pairs[i][1];
            }
            return count;
            
        }
    private:
        static bool cmp(vector<int>& a, vector<int>& b)
        {
            return a[0] < b[0];
        }
            
    };
    

Log in to reply
 

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