Maximum length of pair chain

Array Dynamic Programming Greedy Sorting

61.6% acceptance

Feb 20, 2026

4890

137

Given pairs where pair p2 follows p1 if p1[1] < p2[0], return the length of the longest chain.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn find_longest_chain(mut pairs: Vec<Vec<i32>>) -> i32 {
    pairs.sort_unstable_by_key(|p| p[1]);
    let mut count = 0;
    let mut cur_end = i32::MIN;
    for p in &pairs {
      if p[0] > cur_end {
        count += 1;
        cur_end = p[1];
      }
    }
    count
  }
}