646. Maximum Length of Pair Chain

Medium

3K

113

You are given an array of `n`

pairs `pairs`

where `pairs[i] = [left`

and _{i}, right_{i}]`left`

._{i} < right_{i}

A pair `p2 = [c, d]`

**follows** a pair `p1 = [a, b]`

if `b < c`

. A **chain** of pairs can be formed in this fashion.

Return *the length longest chain which can be formed*.

You do not need to use up all the given intervals. You can select pairs in any order.

**Example 1:**

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

**Example 2:**

Input:pairs = [[1,2],[7,8],[4,5]]Output:3Explanation:The longest chain is [1,2] -> [4,5] -> [7,8].

**Constraints:**

`n == pairs.length`

`1 <= n <= 1000`

`-1000 <= left`

_{i}< right_{i}<= 1000

Accepted

136.6K

Submissions

241.4K

Acceptance Rate

56.6%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved