O(nlogn) solution w/ Python & C++


  • 0
    Z

    it is same as course schedule problem.

    python solution:

    class Solution(object):
        def findLongestChain(self, pairs):
            pairs = sorted(pairs)
            result = 1
            end = pairs[0][1]
            for i in xrange(1, len(pairs)):
                if pairs[i][0] <= end:
                    end = min(end, pairs[i][1])
                else:
                    result += 1
                    end = pairs[i][1]
            return result
    

    c++ solution

    class Solution {
    public:
        int findLongestChain(vector<vector<int>>& pairs) {
            sort(pairs.begin(), pairs.end());
            int count = 1, end = pairs[0][1];
            for ( auto & p : pairs ) {
                if ( p[0] <= end ) {
                    end = min(end, p[1]);
                } else {
                    ++count;
                    end = p[1];
                }
            }
            return count;
        }
    };
    

Log in to reply
 

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