Question

Code

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        
        '''
            dp solution
        '''

        # # Since it does not need to follow the original order
        # pairs.sort()

        # n = len(pairs)

        # dp = [1] * n

        # ans = 1

        # for i in range(n - 1, -1, -1):
        #     for j in range(i + 1, n):
        #         if pairs[j][0] > pairs[i][1]:
        #             dp[i] = max(dp[i], dp[j] + 1)


        # return max(dp) 

        '''
            greedy solution
        '''

        # By greedly taking the pair with later end value

        pairs.sort(key = lambda x:x[1])

        ans = 1

        prev_end = pairs[0][1]

        for left, right in pairs:
            if left > prev_end:
                ans += 1
                prev_end = right


        return ans