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


    class Solution {
    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;
            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.