<p>You are given a 2D array of integers <code>envelopes</code> where <code>envelopes[i] = [w<sub>i</sub>, h<sub>i</sub>]</code> represents the width and the height of an envelope.</p>

<p>One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope&#39;s width and height.</p>

<p>Return <em>the maximum number of envelopes you can Russian doll (i.e., put one inside the other)</em>.</p>

<p><strong>Note:</strong> You cannot rotate an envelope.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> envelopes = [[5,4],[6,4],[6,7],[2,3]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The maximum number of envelopes you can Russian doll is <code>3</code> ([2,3] =&gt; [5,4] =&gt; [6,7]).
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> envelopes = [[1,1],[1,1],[1,1]]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= envelopes.length &lt;= 10<sup>5</sup></code></li>
	<li><code>envelopes[i].length == 2</code></li>
	<li><code>1 &lt;= w<sub>i</sub>, h<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution {
public:
    static bool mycomp(vector<int>& a, vector<int>& b){
        if(a[0]==b[0]){
            return a[1]>b[1];
        }
        return a<b;
    }
    bool check(vector<int> curr, vector<int> prev){
        if(curr[0]>prev[0] && curr[1]>prev[1]){
            return true;
        }
        return false;
    }

    // int mem(int curr, int prev, vector<vector<int>>& envelopes, vector<vector<int>>& dp){
    //     if(curr>=envelopes.size()){
    //         return 0;
    //     }

    //     if(dp[curr][prev+1]!=-1){
    //         return dp[curr][prev+1];
    //     }

    //     int inc = 0;
    //     if(curr==0 || check(curr, prev, envelopes)){
    //         inc = 1 + mem(curr+1, curr, envelopes, dp);
    //     }
    //     int exc = 0 + mem(curr+1, prev, envelopes, dp);
    //     int ans = max(inc, exc);

    //     dp[curr][prev+1] = ans;
    //     return ans;
    // }

    // int tab(vector<vector<int>>& envelopes){
    //     int n = envelopes.size();
    //     vector<vector<int>> dp(n+1, vector<int>(n+1, 0));

    //     for(int curr=n-1; curr>=0; curr--){
    //         for(int prev=curr-1; prev>=-1; prev--){
    //             int inc = 0;
    //             if(prev==-1 || check(curr, prev, envelopes)){
    //                 inc = 1 + dp[curr+1][curr+1];
    //             }
    //             int exc = 0 + dp[curr+1][prev+1];
    //             int ans = max(inc, exc);

    //             dp[curr][prev+1] = ans;
    //         }
    //     }
    //     return dp[0][0];
    // }

    // int SO(vector<vector<int>>& envelopes){
    //     int n = envelopes.size();
    //     vector<int> up(n+1, 0);
    //     vector<int> down(n+1, 0);

    //     for(int curr=n-1; curr>=0; curr--){
    //         for(int prev=curr-1; prev>=-1; prev--){
    //             int inc = 0;
    //             if(prev==-1 || check(curr, prev, envelopes)){
    //                 inc = 1 + down[curr+1];
    //             }
    //             int exc = 0 + down[prev+1];
    //             int ans = max(inc, exc);

    //             up[prev+1] = ans;
    //         }
    //         down = up;
    //     }
    //     return up[0];
    // }

    int solve(int s, int e, vector<vector<int>>& ans, vector<int> num){
        
        int mid = s+(e-s)/2;

        while(s<e){
            if(check(num, ans[mid])){
                s = mid+1;
            }
            else{
                e = mid;
            }
            mid = s+(e-s)/2;
        }

        return e;
    }
    int Opt(vector<vector<int>>& envelopes){
        vector<vector<int>> ans;

        for(int i=0; i<envelopes.size(); i++){
            if(i==0 || check(envelopes[i], ans[ans.size()-1])){
                ans.push_back(envelopes[i]);
                cout<<i<<endl;
            }
            else{
                int target = solve(0, ans.size()-1, ans ,envelopes[i]);
                ans[target] = envelopes[i];
            }
        }

        for(int i=0; i<ans.size(); i++){
            for(int j=0; j<ans[0].size(); j++){
                cout<<ans[i][j]<<" ";
            }
            cout<<"    ";
        }

        return ans.size();
    }

    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        sort(envelopes.begin(), envelopes.end(), mycomp);

        for(int i=0; i<envelopes.size(); i++){
            for(int j=0; j<envelopes[0].size(); j++){
                cout<<envelopes[i][j]<<" ";
            }
            cout<<"    ";
        }
        cout<<endl;

        // vector<vector<int>> dp(n+1, vector<int>(n+1, -1));
        // return mem(0, -1, envelopes, dp);

        // return tab(envelopes);

        // return SO(envelopes);

        return Opt(envelopes);
    }
};
169678