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.

Examples

Example 1:

1
2
3
4
5

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

Example 2:

1
2
3
4
5

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

Solution

Method 1 - Greedy

Intuition

Sort the pairs by their end value. Always pick the next pair whose start is greater than the end of the last selected pair. This greedy approach ensures the longest chain.

Approach

Sort the pairs by their second value. Iterate through the sorted pairs, and for each, if its start is greater than the end of the last selected pair, increment the chain length and update the end.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) { return a[1] < b[1]; });
        int cur = INT_MIN, ans = 0;
        for (const auto& p : pairs) {
            if (p[0] > cur) {
                cur = p[1];
                ++ans;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import "sort"
func findLongestChain(pairs [][]int) int {
    sort.Slice(pairs, func(i, j int) bool { return pairs[i][1] < pairs[j][1] })
    cur, ans := -1<<31, 0
    for _, p := range pairs {
        if p[0] > cur {
            cur = p[1]
            ans++
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public int findLongestChain(int[][] pairs) {
    Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
    int cur = Integer.MIN_VALUE, ans = 0;
    for (int[] p : pairs) {
        if (p[0] > cur) {
            cur = p[1];
            ans++;
        }
    }
    return ans;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

fun findLongestChain(pairs: Array<IntArray>): Int {
    pairs.sortBy { it[1] }
    var cur = Int.MIN_VALUE
    var ans = 0
    for (p in pairs) {
        if (p[0] > cur) {
            cur = p[1]
            ans++
        }
    }
    return ans
}
1
2
3
4
5
6
7
8
9

class Solution:
    def findLongestChain(self, pairs: list[list[int]]) -> int:
        pairs.sort(key=lambda x: x[1])
        cur, ans = float('-inf'), 0
        for p in pairs:
            if p[0] > cur:
                cur = p[1]
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn find_longest_chain(mut pairs: Vec<Vec<i32>>) -> i32 {
        pairs.sort_by_key(|p| p[1]);
        let mut cur = i32::MIN;
        let mut ans = 0;
        for p in pairs {
            if p[0] > cur {
                cur = p[1];
                ans += 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

function findLongestChain(pairs: number[][]): number {
    pairs.sort((a, b) => a[1] - b[1]);
    let cur = -Infinity, ans = 0;
    for (const p of pairs) {
        if (p[0] > cur) {
            cur = p[1];
            ans++;
        }
    }
    return ans;
}

Complexity

  • ⏰ Time complexity: O(n log n), where n is the number of pairs (for sorting).
  • 🧺 Space complexity: O(1), as only a few variables are used.