C++ without dp


  • 0
    W

    the idea is to sort the second value of a pair. O(nlogn)
    and using linear complexity to compare pair[cur][0] and pair[cur-1][1]
    For example, a sequence below:
    [[1, 2],[3, 5000],[4, 50],[8, 10], [12, 14]]
    Instead, we should think this as
    [[1, 2],[8, 10], [12, 14], [4, 50], [3, 5000]]

    bool sortMethod(const vector<int>& a,const vector<int> & b)
    {
    	return a[1] < b[1];
    }
    
    class Solution {
    public:
        int findLongestChain(vector<vector<int>>& pairs) {
    		if (pairs.empty())
    			return 0;
    		
    		sort(begin(pairs), end(pairs), sortMethod);
    		int num = 0;
    
    		int maxPostOrder = pairs[0][1];
    		for (int i = 1; i < pairs.size(); ++i)
    		{
    			if (pairs[i][0] > maxPostOrder)
    			{
    				num++;
    				maxPostOrder = pairs[i][1];
    			}
    		}
    
    		return num+1;
        }
    };
    `

Log in to reply
 

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