Problem Summary

You are given an array of pairs, where each pair is a two-element array [a, b].

A pair [a, b] can be chained with [c, d] if and only if:

b < c

Your task is to find the maximum length of a chain you can form.

Example
Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: You can form the chain [1,2] -> [3,4].

Example
Input: [[1,2], [7,8], [4,5]]
Output: 3
Explanation: Chain: [1,2] -> [4,5] -> [7,8].

Constraints

• Number of pairs: up to a few thousand
• Pairs may be unsorted
• Greedy solutions are expected

---

Approach (Simple English)

This problem is directly related to the classic activity selection or interval scheduling problem.

Key Idea

Sort all pairs based on their ending value (b).
Then greedily pick the pair with the earliest end, and keep selecting next pairs whose start is greater than the current end.

Why This Works

Choosing the pair that ends earliest always leaves the maximum possible room for future selections.
This is the same reasoning used in the interval scheduling maximum non-overlapping problem.

It gives an optimal solution.

Steps

1. Sort the pairs by their second value (pair[1]).
2. Initialize:
   • currentEnd = -∞
   • count = 0
3. For each pair [a, b] in sorted order:
   • If a > currentEnd, you can chain it:
     • count++
     • currentEnd = b
4. Return count.

The greedy strategy is optimal and runs in O(n log n).

---

Java Code (Greedy Optimal Solution)

import java.util.Arrays;

class Solution {
    public int findLongestChain(int[][] pairs) {

        // Sort by second value of each pair
        Arrays.sort(pairs, (p1, p2) -> Integer.compare(p1[1], p2[1]));

        int count = 0;
        int currentEnd = Integer.MIN_VALUE;

        for (int[] pair : pairs) {
            if (pair[0] > currentEnd) {
                count++;
                currentEnd = pair[1];
            }
        }
        return count;
    }
}

This is the simplest and fastest solution.

---

Alternative Approach: Dynamic Programming (O(n²))

Less efficient but matches the LIS (Longest Increasing Subsequence) style DP.

DP Idea

Sort pairs by the first value (a).
Compute dp[i] = longest chain ending at pair i.

Transition:

if pairs[j][1] < pairs[i][0]:  
    dp[i] = max(dp[i], dp[j] + 1)

Time complexity: O(n²), which is slower than greedy and not required.

---

Dry Run (Greedy Approach)

Input
pairs = [[1,2], [7,8], [4,5]]

Step 1: Sort by second value

Sorted:
[[1,2], [4,5], [7,8]]

Step 2: Initialize

currentEnd = -∞
count = 0

Step 3: Traverse

• [1,2]:
  1 > -∞ → take
  count = 1
  currentEnd = 2
• [4,5]:
  4 > 2 → take
  count = 2
  currentEnd = 5
• [7,8]:
  7 > 5 → take
  count = 3
  currentEnd = 8

Final answer = 3

---

Complexity Analysis

Greedy approach:
Time: O(n log n) (sorting)
Space: O(1) or O(log n) depending on sort implementation

DP approach:
Time: O(n²)
Space: O(n)

Greedy is preferred and optimal.

---

Edge Cases

• All pairs disjoint → chain length = number of pairs
• Fully overlapping pairs → chain length = 1
• Empty input → return 0
• Negative intervals handled naturally since sorting uses value comparison