# LeetCode 646: Maximum Length of Pair Chain

## Problem Restatement

We are given a list of integer pairs.

Each pair looks like:

```python
[left, right]
```

A pair:

```python
[a, b]
```

can be followed by:

```python
[c, d]
```

if:

```python
b < c
```

We need to build the longest possible chain of pairs.

Return the maximum chain length.

The constraints guarantee:

```python
left < right
```

for every pair.

## Input and Output

| Item | Meaning |
|---|---|
| Input | List of integer pairs |
| Output | Maximum valid chain length |
| Chain rule | `[a, b]` can connect to `[c, d]` only if `b < c` |

Example function shape:

```python
def findLongestChain(pairs: list[list[int]]) -> int:
    ...
```

## Examples

Example 1:

```python
pairs = [[1, 2], [2, 3], [3, 4]]
```

Possible chains:

| Chain | Valid? |
|---|---|
| `[1,2] -> [2,3]` | No, because `2 < 2` is false |
| `[1,2] -> [3,4]` | Yes |
| `[2,3] -> [3,4]` | No, because `3 < 3` is false |

The best chain is:

```python
[1,2] -> [3,4]
```

Length:

```python
2
```

Example 2:

```python
pairs = [[1, 2], [7, 8], [4, 5]]
```

We can chain all three:

```python
[1,2] -> [4,5] -> [7,8]
```

So the answer is:

```python
3
```

## First Thought: Try All Chains

A brute force solution would try every subset and every ordering.

This is too expensive because the number of possible chains grows exponentially.

We need to recognize the structure of the problem.

## Key Insight

This problem is almost identical to interval scheduling.

Each pair behaves like an interval:

```text
[start, end]
```

To maximize how many intervals we can take, the classic greedy strategy is:

```text
Always choose the interval with the smallest ending value first.
```

Why?

A smaller ending value leaves more room for future pairs.

So:

1. Sort pairs by their second value.
2. Greedily pick pairs whenever they can extend the current chain.

## Why Sorting by End Works

Suppose we have:

```python
[1, 10]
[2, 3]
[4, 5]
```

If we choose `[1,10]` first, we cannot take anything else.

But if we choose the pair with the smallest ending value first:

```python
[2,3]
```

then we can also take:

```python
[4,5]
```

This gives a longer chain.

## Algorithm

1. Sort pairs by their second value.
2. Initialize:
   1. `count = 0`
   2. `current_end = -infinity`
3. Scan the sorted pairs:
   1. If the current pair starts after `current_end`, take it.
   2. Increase `count`.
   3. Update `current_end`.
4. Return `count`.

## Implementation

```python
class Solution:
    def findLongestChain(self, pairs: list[list[int]]) -> int:
        pairs.sort(key=lambda pair: pair[1])

        count = 0
        current_end = float("-inf")

        for left, right in pairs:
            if current_end < left:
                count += 1
                current_end = right

        return count
```

## Code Explanation

First, we sort by the ending value:

```python
pairs.sort(key=lambda pair: pair[1])
```

This ensures we always consider the earliest-finishing pair first.

We track the end value of the last chosen pair:

```python
current_end = float("-inf")
```

Initially, any pair can be chosen.

For each pair:

```python
if current_end < left:
```

If the current pair starts after the previous chosen pair ends, it can extend the chain.

So we take it:

```python
count += 1
current_end = right
```

At the end, `count` is the maximum chain length.

## Correctness

The algorithm always selects the available pair with the smallest ending value.

Suppose the algorithm selects pair `A`, while some optimal solution selects a different compatible pair `B` first.

Because the pairs are sorted by ending value, the end of `A` is less than or equal to the end of `B`.

Therefore, replacing `B` with `A` cannot reduce the number of future pairs that can still be chosen, since `A` finishes no later than `B`.

So every optimal solution can be transformed into another optimal solution that begins with the greedy choice.

After choosing the first pair, the remaining problem has the same structure: find the maximum chain among pairs starting after the chosen end value.

By repeatedly applying the same argument, the greedy algorithm constructs an optimal chain.

Therefore, the returned chain length is maximum.

## Complexity

Let `n = len(pairs)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | Sorting dominates |
| Space | `O(1)` or `O(log n)` | Depends on sorting implementation |

## Alternative Solution: Dynamic Programming

We can also use DP.

Sort pairs by start value.

Let:

```python
dp[i]
```

mean:

```text
maximum chain length ending at pair i
```

Transition:

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

Implementation:

```python
class Solution:
    def findLongestChain(self, pairs: list[list[int]]) -> int:
        pairs.sort()

        n = len(pairs)
        dp = [1] * n

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

        return max(dp)
```

| Metric | Value |
|---|---:|
| Time | `O(n²)` |
| Space | `O(n)` |

The greedy solution is simpler and faster.

## Connection to Activity Selection

This problem is the same core structure as:

| Problem | Shared Idea |
|---|---|
| Activity Selection | Choose earliest finishing interval |
| Non-overlapping Intervals | Greedy by end time |
| Meeting Room Scheduling | Earliest ending leaves more space |

The key pattern is:

```text
When maximizing the number of non-overlapping intervals, sort by ending time.
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.findLongestChain([[1, 2], [2, 3], [3, 4]]) == 2
    assert s.findLongestChain([[1, 2], [7, 8], [4, 5]]) == 3
    assert s.findLongestChain([[1, 10], [2, 3], [4, 5]]) == 2
    assert s.findLongestChain([[5, 24], [15, 25], [27, 40], [50, 60]]) == 3
    assert s.findLongestChain([[-10, -1], [0, 2], [3, 5]]) == 3
    assert s.findLongestChain([[1, 100]]) == 1

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[[1,2],[2,3],[3,4]]` | Strict inequality matters |
| Fully chainable pairs | All pairs can be used |
| Large interval trap | Greedy must avoid long blocking interval |
| Mixed intervals | Standard scheduling behavior |
| Negative values | Ordering still works |
| Single pair | Minimum non-empty case |