Java solution, 10 lines, DP


  • 6

    Reference: http://www.geeksforgeeks.org/dynamic-programming-set-20-maximum-length-chain-of-pairs/

    public class Solution {
        public int findLongestChain(int[][] pairs) {
            Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
            
            int i, j, max = 0, n = pairs.length;
            int dp[] = new int[n];
          
            for (i = 0; i < n; i++) dp[i] = 1;
            
            for (i = 1; i < n; i++)
                for (j = 0; j < i; j++)
                    if (pairs[i][0] > pairs[j][1] && dp[i] < dp[j] + 1)
                        dp[i] = dp[j] + 1;
    
            for (i = 0; i < n; i++) if (max < dp[i]) max = dp[i];
            
            return max;
        }
    }
    

  • 0
    J

    Ah, good solution


  • 1
    L

    same idea, got TLE using python....


  • 2
    M

    Just some thoughts on this problem.

    Sorting on either the first element or the second, this problem essentially reduces to the Longest Increasing Subsequence problem and we can use DP to solve it.

    However, if we want to use Greedy to solve this problem, we need to sort on the second element. Sorting on the first element will not work. For example, try (8,9) (10,11) (1,100).

    My initial trial uses DFS+memorization. It is not efficient in both time and space though.

    DFS + memorization:

    class Solution {
    public:
        int findLongestChain(vector<vector<int>>& pairs) {
            vector<bool> visited(pairs.size(), false);
            vector<int> record(pairs.size(), 0);
            int max_depth = 1;
            for(int i=0; i<pairs.size(); i++) {
                visited[i]=true;
                int depth = dfs(pairs,visited,i,record);
                max_depth = max(max_depth,depth);
                visited[i]=false;
            }
            return max_depth;
        }
    private:
        int dfs(const vector<vector<int>>& pairs, vector<bool>& visited, int index, vector<int>& record) {
            int max_depth = 0;
            for(int i=0; i<pairs.size(); i++) {
                if(!visited[i] && pairs[i][0]>pairs[index][1]) {
                    visited[i] = true;
                    int depth = getOrUpdate(pairs,visited,i,record);
                    max_depth = max(max_depth,depth);
                    visited[i] = false;
                }
            }
            return max_depth+1;
        }
        int getOrUpdate(const vector<vector<int>>& pairs, vector<bool>& visited, int index, vector<int>& record) {
            if(record[index]!=0) return record[index];
            return record[index] = dfs(pairs,visited,index,record);
        }
    };
    

  • 0

    I understand your dp, it's like job schedule problem, but can you explain why if I use the finish time to sort the array, i.e. change the 3rd line to
    Arrays.sort(pairs, (a, b) -> (a[1] - b[1])); it's also accepted?


    I also came up with dfs when first saw this problem, I considered it as a permutation problem but got TLE.

        int max = 1;
    
        public int findLongestChain(int[][] pairs) {
            if (pairs == null || pairs.length == 0) return 0;
            Arrays.sort(pairs, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0] - o2[0];
                }
            });
            chainDfs(0, pairs, new boolean[pairs.length], 0, Integer.MIN_VALUE);
            return max;
        }
    
        private void chainDfs(int index, int[][] pairs, boolean[] used, int count, int b) {
            if (index == pairs.length)
                return;
            for (int i = index; i < pairs.length; i++) {
                if (!used[i] && pairs[i][0] > b) {
                    used[i] = true;
                    max = Math.max(count + 1, max);
                    chainDfs(i + 1, pairs, used, count + 1, pairs[i][1]);
                    used[i] = false;
                }
            }
        }
    

  • 0
    J

    First sort the pairs by first element. DP solution, for i-th pair the longest chain will be equal to 1 + the first longest chain to the left of i-th pair.

    public class Solution {
        public int findLongestChain(int[][] pairs) {
    
            Arrays.sort(pairs, new Comparator<int[]>() {
                public int compare(final int[] a, final int[] b) {
                    return a[0] - b[0];
                }   
            });
    
            int n = pairs.length;
    
            int[] d = new int[n];
    
            for (int i = 0; i < n; i++) {
                int counter = 1;
    
                for (int j = i - 1; j >= 0; j--) {
                    if (pairs[i][0] > pairs[j][1]) {
                        counter += d[j];
    
                        break;
                    }
                }
    
                d[i] = counter;
            }
    
            return d[n - 1];
        }
    }

  • 5
        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];
        }
    

  • 1

    This result is a little bit weird because most people like handle from head to tail but this result is handle from tail to head.
    I update the answer to think as a normal human being.

    class Solution {
    public int findLongestChain(int[][] pairs) {
    Arrays.sort(pairs, (a, b) -> (a[1] - b[1]));

        int result = 0;
        int[] dp = new int[pairs.length];
        
        for (int i = 0; i < pairs.length; i++) {
            dp[i] = 1;
        }
        for (int i = 0; i < pairs.length - 1; i++) {
            for (int j = i + 1; j < pairs.length; j++) {
                if (pairs[j][0] > pairs[i][1] && dp[j] < dp[i] + 1) { 
                    dp[j] = dp[i] + 1; 
                }
            }
        }
        for (int i = 0; i < pairs.length; i++) {
            if (result < dp[i]) {
                result = dp[i];
            }
        }
        return result;
    }
    

    }


  • 0
    H

    @shawngao said in Java solution, 10 lines, DP:

    public class Solution {
    public int findLongestChain(int[][] pairs) {
    Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));

        int i, j, max = 0, n = pairs.length;
        int dp[] = new int[n];
      
        for (i = 0; i < n; i++) dp[i] = 1;
        
        for (i = 1; i < n; i++)
            for (j = 0; j < i; j++)
                if (pairs[i][0] > pairs[j][1] && dp[i] < dp[j] + 1)
                    dp[i] = dp[j] + 1;
    
        for (i = 0; i < n; i++) if (max < dp[i]) max = dp[i];
        
        return max;
    }
    

    }

    I think the last loop is unnecessary.


Log in to reply
 

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