646. Maximum Length of Pair Chain - cocoder39/coco39_LC GitHub Wiki

646. Maximum Length of Pair Chain

Notes 2020:

Option 1: DP T = O(n^2)

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort()
        n = len(pairs)
        dp = [1] * n
        res = 0
        for i in range(n):
            for j in range(i):
                if pairs[i][0] > pairs[j][1]:
                    dp[i] = max(dp[i], dp[j] + 1)
            res = max(res, dp[i])
        return res

Option 2: greedy T = O(n)

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        cur = -float('inf')
        res = 0
        for start, end in sorted(pairs, key=lambda pair: pair[1]):
            if start > cur:
                cur = end
                res += 1
        return res
  • suppose A = (a1, a2) B = (b1, b2)
  • if a2 < b2, then we should first append A Proof:
    • if a2 < b1, A and B have no overlap so it is clear A should be appended first
    • if a2 >= b1, appending either A or B will increase the chain by one but A is preferred since A[1] is smaller.

========================================================

Arrays.sort(pairs, (a, b) -> a[1] - b[1]);

Greedy :O(n * log n) time from sorting and O(n) space from sorting

public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b)
            {
                if (a[1] == b[1]) {
                    return a[0] - b[0];
                }
                return a[1] - b[1];
            }
        });
        
        int res = 1;
        int cur = pairs[0][1];
        for (int i = 1; i < pairs.length; i++) {
            if (pairs[i][0] > cur) {
                res++;
                cur = pairs[i][1];
            }
        }
        return res;
    }

dp: sorting - O(n) space and O(n*logn) time dp - O(n) space and O(n^2) time

public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b)
            {
                if (a[1] == b[1]) {
                    return a[0] - b[0];
                }
                return a[1] - b[1];
            }
        });
        int dp[] = new int[pairs.length];
        int res = 0;
        
        for (int i = 0; i < pairs.length; i++) {
            dp[i] = helper(pairs, dp, i);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
                         
    private int helper(int[][] pairs, int dp[], int i) {
        int res = 1;
        for (int j = i - 1; j >= 0; j--) {
            if (pairs[i][0] > pairs[j][1]) {
                res = Math.max(res, dp[j] + 1);
            }
        }
        return res;
    }
⚠️ **GitHub.com Fallback** ⚠️