C++ Greedy Solution. O(nlogn)

  • 0

    First, sort the interval by increasing order. O(nlogn)
    Second, loop the pairs, keep the minimum end value if multiple pairs overlap.
    If no overlap, then the chain count + 1, also update the minimum end.

    class Solution {
        int findLongestChain(vector<vector<int>>& pairs) {
            sort(pairs.begin(), pairs.end(), [](vector<int> l, vector<int> r) 
                 { if(l[0] == r[0]){ return l[1] < r[1];}
                     return l[0] < r[0];});
            int len = 1;
            int min_end = pairs[0][1];
            for(int i = 1; i < pairs.size(); i++){
                if(min_end >= pairs[i][1]){
                    min_end = pairs[i][1];
                } else if(min_end < pairs[i][0]){
                    min_end = pairs[i][1];
            return len;

Log in to reply

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