[646. Maximum Length of Pair Chain] C++_sort and greedy algorithm


  • 0

    Pretty straightforward problem. We always choose the range with smaller start number, and short length so that we can add as many as ranges into our final result.

    Code:

    class Solution {
    public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), [](vector<int> a, vector<int> b){
            return a[1] < b[1] || (a[1] == b[1] && a[0] > b[0]);
        });
        int res = 1, e = pairs[0][1];
        for(int i = 1; i < pairs.size(); ++i){
            if(pairs[i][0] <= e) continue;
            res++;
            e = pairs[i][1];
        }
        return res;
    }
    };

Log in to reply
 

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