Problem statement

https://leetcode.com/problems/maximum-length-of-pair-chain/

Solution

Basically, almost the same as problem 0435 Non-overlapping Intervals, but here we need to find the maximum number of non-overlapping intervals and they can not have the same ends.

Complexity

Time complexity is O(n log n), space is O(n).

Code

class Solution:
    def findLongestChain(self, pairs):      
        count, curr = 0, -float("inf")
        for x, y in sorted(pairs, key = lambda x: x[1]):
            if curr < x:
                count += 1
                curr = y        
        return count

It can also be solved with DP in O(n^2), similar to Problem 0300 Longest Increasing Subsequence.