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.

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