Russian dolls Envelopes -LeetCode C++

Russian Dolls.cpp

//SOLUTION 1 - DP O(N<sup>2</sup>)

class Solution {
public:
  static  bool compare (vector<int>& i, vector<int>& j) {
        return i[0]*i[1] <j[0]*j[1];
    }
   int maxEnvelopes(vector<vector<int>>& envelopes) {
       sort(envelopes.begin(), envelopes.end(), compare);
            int N = envelopes.size();
            vector<int> dp(N, 1);
            int mx = (N == 0) ? 0 : 1;
            
            for (int i = 0; i < N; i++) {
                for (int j = i - 1; j >= 0; j--) {
                    if (envelopes[j][0]<envelopes[i][0] && envelopes[j][1]<envelopes[i][1] ) {
                        dp[i] = max(dp[i], dp[j] + 1);
                        mx = max(dp[i], mx);
                    }
                }
            }
            return mx;
        }
};


--------------------------------------------------------------------------------------------------------------------------------
//SOLUTION 2 -binary search O(nlogn)
class Solution {
public:
    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        vector<int> dp;
		sort(envelopes.begin(), envelopes.end(), [](const pair<int, int> &a, const pair<int, int> &b){
			if (a.first == b.first) return a.second > b.second;
			return a.first < b.first;
		});
		for (int i = 0; i < envelopes.size(); ++i) {
			int left = 0, right = dp.size(), t= envelopes[i].second;
			while (left < right) {
				int mid = left + (right - left) / 2;
				if (dp[mid] < t) left = mid + 1;
				else right = mid;
			}
			if (right >= dp.size()) dp.push_back(t);
			else dp[right] = t;
		}
		return dp.size();
    }
};