# Maximum Length of Pair Chain

## Description

You are given `n` pairs of numbers. In every pair, the first number is always smaller than the second number.

Now, we define a pair `(c, d)` can follow another pair `(a, b)` if and only if `b < c`. Chain of pairs can be formed in this fashion.

Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.

**Example 1:**

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

**Note:**

1. The number of given pairs will be in the range \[1, 1000].

## Solution

This is a typical scheduling problem. Use a greedy algorithm that repeatedly selects the time-slots with the earliest end time.

Proof: Let $$G, O$$ be the greedy and optimal solutions, respectively. Let $$g\_i, o\_i$$ be the first time-slot that they differ. We can convert $$o\_i$$ to $$g\_i$$ to get a "greedier" optimal solution $$O'$$. By doing the conversion repeatedly we can eventually convert $$O$$ to $$G$$. Therefore, $$G$$ is also an optimal solution.

```cpp
class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), [](vector<int> &p1, vector<int> &p2){
           return p1[1] < p2[1];
        });
        int count = 1;
        int endTime = pairs[0][1];
        for(int i = 1; i < pairs.size(); ++i){
            if(pairs[i][0] > endTime){
                ++count;
                endTime = pairs[i][1];
            }
        }
        return count;
    }
};
```

(Implementation optimization trick: because the sorting dominates the running time, convert `pairs` to type `vector<pair<int, int>>` to speed up.)