WEEK#5 Dynamic Programming_Maximum Length of Pair Chain

Description of the Problem

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:
The number of given pairs will be in the range [1, 1000].

A rough idea

1.Sort the pairs by their smaller number
2.Select the first pair, who has the smallest first number, and set smallest = 0
3.Traverse all pairs by i

1. if SmallestPair[smallest][1] < CurrentPair[i][0]
2. result++; smallest = i;

    bool SortFunction(vector<int> v1, vector<int> v2) {
        return v1[0] < v2[0];
    }

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), SortFunction);
        int result = 1;
        int Min = pairs[0][0]; // minimun number in all pairs
        int MinIndex = 0; // index of pairs in which minimun number exists
        for (int i = 0 ; i < pairs.size(); i++) {
            if (pairs[MinIndex][1] < pairs[i][0]) {
                Min = pairs[i][0];
                MinIndex = i;
                result++;
            }
        }
        return result;
    }
};

Such program gets a wrong answer :

WA.png

Analysis:

Having neglected the situations where the first number be the smallest of all and the second number be the largest of all. In this way, the length of the chain would be only 1.

Correction

Sort by the larger number. Because the smaller the larger number is, the bigger the range in which we can select.

    bool SortFunction(vector<int> v1, vector<int> v2) {
        return v1[1] < v2[1];
    }

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), SortFunction);
        int result = 1;
        int Min = pairs[0][0]; // minimun number in all pairs
        int MinIndex = 0; // index of pairs in which minimun number exists
        for (int i = 0 ; i < pairs.size(); i++) {
            if (pairs[MinIndex][1] < pairs[i][0]) {
                Min = pairs[i][0];
                MinIndex = i;
                result++;
            }
        }
        return result;
    }
};

AC.png

Not exactly an ideal solution though. Should look for improvement.