C++ Greedy Solution. O(nlogn)


  • 0
    D

    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 {
    public:
        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]){
                    len++;
                    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.