C++ O(nlogn) Time, O(1) Space


  • 0
    L

    I think it is a greedy algorithm. Does anyone have the O(n) Time solution to share? Or prove that it can not be better than O(nlogn)?

    class Solution {
    public:
        int findLongestChain(vector<vector<int>>& pairs) {
            if (pairs.size() == 0) return 0;
            sort(pairs.begin(), pairs.end(), [] (const vector<int>& x, const vector<int>& y) { return y[1] > x[1]; });
            int ans = 1, cur = 0;
            for (int i = 1; i < pairs.size(); i++) {
                if (pairs[i][0] > pairs[cur][1]) {
                    ans++;
                    cur = i;
                }
            }
            return ans;
        }
    };
    

Log in to reply
 

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