Last updated on February 4th, 2025 at 12:23 am

Here, we see a Maximum Length of Pair Chain LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Dynamic Programming

Companies

Amazon

Level of Question

Medium

Maximum Length of Pair Chain LeetCode Solution

1. Problem Statement

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.

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

2. Coding Pattern Used in Solution

The coding pattern used in this code is “Greedy Algorithm”. The problem involves selecting the maximum number of non-overlapping intervals (or chains) from a list of pairs. The greedy approach works here because we sort the pairs by their ending times and always pick the next pair that starts after the current pair ends. This ensures that we maximize the number of chains.

3. Code Implementation in Different Languages

3.1 Maximum Length of Pair Chain C++

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        int cur = INT_MIN, ans = 0;
        for (const auto& pair : pairs) {
            if (cur < pair[0]) {
                cur = pair[1];
                ans++;
            }
        }
        return ans;        
    }
};

3.2 Maximum Length of Pair Chain Java

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> Integer.compare(a[1], b[1]));
        int cur = Integer.MIN_VALUE, ans = 0;
        for (int[] pair : pairs) {
            if (cur < pair[0]) {
                cur = pair[1];
                ans++;
            }
        }
        return ans;        
    }
}

3.3 Maximum Length of Pair Chain JavaScript

var findLongestChain = function(pairs) {
    pairs.sort((a, b) => a[1] - b[1]);
    let cur = Number.MIN_SAFE_INTEGER, ans = 0;
    for (const [start, end] of pairs) {
        if (cur < start) {
            cur = end;
            ans++;
        }
    }
    return ans;    
};

3.4 Maximum Length of Pair Chain Python

class Solution(object):
    def findLongestChain(self, pairs):
        pairs.sort(key=lambda x: x[1])
        cur, ans = float('-inf'), 0
        for pair in pairs:
            if cur < pair[0]:
                cur = pair[1]
                ans += 1      
        return ans

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	(O(n \log n))	O(1)
Java	(O(n \log n))	O(1)
JavaScript	(O(n \log n))	O(1)
Python	(O(n \log n))	O(1)

The code uses a Greedy Algorithm to solve the problem efficiently. It sorts the pairs by their end times and iterates through them to build the longest chain of non-overlapping intervals. The time complexity is (O(n \log n)) due to sorting, and the space complexity is (O(1)) as no additional data structures are used.