O(nlog(n)) easy to understand solution


  • 0
    I
    bool cmp(vector<int> &a, vector<int> &b){
        return a[1] == b[1] ? a[0] < b[0]: a[1] < b[1];
    }
    class Solution {
    public:    
        int findLongestChain(vector<vector<int>>& pairs) {        
            sort(pairs.begin(),pairs.end(),cmp);
            int last = pairs[0][1];
            int res = 1;
            for(int i = 1; i < pairs.size();++i){
                if(pairs[i][0] > last){
                    ++res;
                    last = 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.