Maximum Length of Pair Chain

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

Constraints:

• n == pairs.length
• 1 <= n <= 1000
• -1000 <= left<sub>i</sub> < right<sub>i</sub> <= 1000

import java.util.Arrays;

class Solution {
    public int findLongestChain(int[][] pairs) {
        // Sort the pairs based on the end value (right value)
        Arrays.sort(pairs, (a, b) -> a[1] - b[1]);

        int chainLength = 0;
        int chainEnd = Integer.MIN_VALUE;

        for (int[] pair : pairs) {
            int start = pair[0];
            int end = pair[1];

            // If the current pair starts after the end of the current chain,
            // we can extend the chain
            if (start > chainEnd) {
                chainLength++;
                chainEnd = end;
            }
        }

        return chainLength;
    }
}

Explanation:

1. Sorting: The core idea is to sort the pairs based on their end values. This allows us to greedily pick pairs that have the smallest end values, maximizing the potential to add more pairs to the chain.
2. Greedy Approach: After sorting, we iterate through the pairs. We keep track of the end value of the current chain (chainEnd). If the start value of the current pair is greater than chainEnd, it means we can extend the chain by including this pair.

Example:

Consider the input pairs = [[1, 2], [2, 3], [3, 4]].

1. Sorting: The pairs remain in the same order after sorting because they are already sorted by the end value.
2. Iteration:
   • [1, 2]: chainEnd is initialized to Integer.MIN_VALUE. Since 1 > Integer.MIN_VALUE, we increment chainLength to 1 and set chainEnd = 2.
   • [2, 3]: Since 2 > 2 is false, we don't extend the chain.
   • [3, 4]: Since 3 > 2, we increment chainLength to 2 and set chainEnd = 4.

Therefore, the longest chain length is 2 (e.g., [1, 2] -> [3, 4]).

Naive Approach

A naive approach would involve trying every possible combination of pairs, which would have exponential time complexity and would not be practical for larger inputs. The recursive approach with memoization can be seen as a slightly less naive approach than brute force.

Optimal Solution

The optimal solution uses a greedy approach after sorting the pairs by their end values. This ensures that we are always picking the pair that allows us to potentially add more pairs to the chain.

Big(O) Run-Time Analysis

• Sorting: Arrays.sort() has a time complexity of O(n log n), where n is the number of pairs.
• Iteration: The loop iterates through each pair once, which takes O(n) time.

Therefore, the overall time complexity is O(n log n), dominated by the sorting step.

Big(O) Space Usage Analysis

• The space complexity is O(1) because we are only using a few extra variables to store the current chain length and the end value of the chain. The sorting is done in-place (depending on the implementation of Arrays.sort(), it might take O(log n) extra space).

Edge Cases and Handling

1. Empty Input: If the input array is empty, the function should return 0. The given code handles this case implicitly as the loop won't execute.
2. Null Input: If the input array is null, it will throw a NullPointerException. You may add a check for null input at the beginning of the function if needed.
3. Pairs with Same End Value: If multiple pairs have the same end value, the order after sorting is not guaranteed to be the same as the input. However, this does not affect the correctness of the algorithm.
4. Pairs with Overlapping Intervals: The algorithm correctly handles overlapping intervals by greedily choosing the pair with the smallest end value, thus maximizing the potential for adding more pairs to the chain.
5. Large Number of Pairs: For a large number of pairs, the O(n log n) time complexity is still efficient, and the O(1) space complexity ensures that the algorithm remains memory-efficient.