#646

Maximum Length of Pair Chain

specialist · 685 · lc medium +30 · verified · 61.6% accepted · 4,893 likes · top 62%

⚑ Longest Increasing Subsequence (LIS)⚑ Interval Scheduling / Merging

Description

Given an array of n pairs where pairs[i] = [left, right] with left < right, a chain is formed by selecting pairs so that each consecutive pair [c, d] starts strictly after the previous pair ends (b < c). Return the maximum number of pairs that can be chained together (pairs may be chosen in any order).

Example 1:

Input: pairs = [[1,2],[2,3],[3,4]]

Output: 2

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

Example 2:

Input: pairs = [[1,2],[7,8],[4,5]]

Output: 3

Explanation: The longest chain is [1,2] -> [4,5] -> [7,8].

Code

1

2

3

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

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