Skip to main content

646. Maximum Length of Pair Chain

medium

Chain pairs (a, b) -> (c, d) where b < c. Find the longest chain. Sort by second element and chain greedily, or treat as LIS-style 1D DP.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given an array of n pairs pairs where pairs[i] = [lefti, righti] and lefti < righti. 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.

Constraints

  • n == pairs.length
  • 1 <= n <= 1000
  • -1000 <= lefti < righti <= 1000

Examples

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].

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Treat it as LIS: dp[i] = longest chain ending at pair i after sorting by left endpoint. O(n^2).

Hint 2

Better: sort by right endpoint. Greedily extend the chain whenever the next pair's left exceeds the current right.

Hint 3

The greedy proof is identical to the activity-selection problem.

Solution approach

Reveal approach

Two equivalent approaches. LIS-style O(n^2) DP: sort pairs by left endpoint, define dp[i] as the longest chain ending at i, and for each i look back at every j with pairs[j][1] < pairs[i][0] and take dp[i] = max(dp[i], dp[j] + 1). Answer is max(dp). Greedy O(n log n) — preferred: sort pairs by right endpoint ascending. Sweep left to right; maintain current_end = -infinity and count = 0. For each pair if pair[0] > current_end then count += 1 and current_end = pair[1]. Return count. The greedy is correct by the standard activity-selection exchange argument — taking the pair that closes earliest never hurts.

Complexity

Time
O(n log n)
Space
O(1)

Related patterns

  • dynamic-programming
  • greedy
  • activity-selection
  • lis

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Maximum Length of Pair Chain and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →