Russian doll envelopes


  • 1
    L

    O(n*logn) solution

    int maxEnvelopes(vector<pair<int, int>>& e) {
    	int n = e.size();
    	if (n < 2) return n;
    
    	sort(e.begin(), e.end(), [&](const pair<int, int> &lhs, const pair<int, int> &rhs) {return lhs.first < rhs.first || lhs.first == rhs.first && lhs.second>rhs.second; });
    
    	vector<int> ret;
    	auto bisearch = [&](int val)
    	{
    		int left = 0, right = ret.size() - 1;
    		while (left <= right)
    		{
    			int mid = (left + right) >> 1;
    			if (ret[mid] < val) left = mid + 1;
    			else right = mid - 1;
    		}
    		return left;
    	};
    
    	for (int i = 0; i < n; i++)
    	{
    		int val = e[i].second;
    		int k = bisearch(val);
    		if (ret.size() <= k)
    			ret.push_back(val);
    		else
    			ret[k] = val;
    	}
    	return ret.size();        
    }

  • 0
    U

Log in to reply
 

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