c++ solution with explanation


  • 0
    L

    1.sort pairs based on their first numbers.
    2.if current pair's first is bigger than last pair's second, then of course we can keep the last pair.
    If not, keep the pair which has a smaller second number.

    int findLongestChain(vector<vector<int>>& pairs) {
            sort(pairs.begin(), pairs.end(), [](const vector<int>& v1, const vector<int>& v2)->bool{return v1[0] < v2[0];});
            int count = 1;
            int back = pairs[0][1];
            for (int i=1; i<pairs.size(); i++) {
                if (pairs[i][0] > back) {
                    count++;
                    back = pairs[i][1];
                } else {
                    back = min(back, pairs[i][1]);
                }
            }
            return count;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.