Leetcode 646. Maximum Length of Pair Chain (Python)

Related Topic

Dynamic-Programming.

Description

You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.

Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.

Given a set of pairs, find the length longest chain which can be formed. You needn’t use up all the given pairs. You can select pairs in any order.

Sample I/O

Example 1

Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]

Note:

The number of given pairs will be in the range [1, 1000].

Methodology

This question can be solved by Dynamic Programming. It is similar with question 300. Longest Increasing Subsequence. However you can also use greedy to solve this question and it has better performance.

First, we need to sort the list then we creat a dp list to memorize the number of increasing subsequence. If the current pair’s first value is greater than prevous pair’s second value, then current number of increasing subsequence is the previous number of increasing subsequence + 1. Finally, we return the max number in dp list

Find the base case:

Init each element of dp list to 1 as there is at least 1 number of increasing subsequence unless the input is empty list.

Find the pattern:

If the current pair’s first value is greater than prevous pair’s second value, then current number of increasing subsequence is the previous number of increasing subsequence + 1.

Answer:

Return the max value of dp

Code 1 (dynamic programming)

def findLongestChain(self, pairs: List[List[int]]) -> int:
        if not pairs: return 0
        size = len(pairs)
        new_pair = sorted(pairs)
        dp=[1]*size
        for i in range(1,size):
            for j in range(i-1,-1,-1):
                if new_pair[i][0]>new_pair[j][1]:
                    dp[i]=max(dp[i],dp[j]+1)
        return max(dp)

BigO

Create dp list will cost O(n) and iterate the dp will cost ((n-1)^2) in total will be O((n-1)^2+2n)