Simple Java solution using DP


  • 0
    A
    public class Solution {
        public int findLongestChain(int[][] pairs) {
            int l = pairs.length;
            if(l == 0){
                return 0;
            }
            int ans = 1;
            Arrays.sort(pairs,(a,b)->Integer.compare(a[0],b[0]));
            
            int lis[] = new int[l];
            int i,j;
            
            Arrays.fill(lis,1);
            for (i = 1; i < l;i++){
                for(j =0;j < i; j++){
                     if (pairs[i][0] > pairs[j][1] && lis[i] < lis[j] + 1)
                        lis[i] = lis[j] + 1;
                }
                ans = Math.max(ans,lis[i]);         
            }
            
            return ans;
                  
        }
    }
    

Log in to reply
 

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