<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:
    bool check(int indx,vector<map<int,int>> &level_row_thrushold_col,vector<int> & a){
        // cout<<indx<<" ";
        auto v = level_row_thrushold_col[indx].upper_bound(a[0]) ;
        if(v==level_row_thrushold_col[indx].begin())return false ;
        else {
            v-- ;
            return (*v).second<=a[1] ;
        }
    }
    int mini(int a,  int b){
        return (a>b)?b:a ;
    }
    int solve(vector<vector<int>> & a){
        vector<map<int,int>> level_row_thrushold_col ;
        map<int,int> t ; t[a[0][0]+1]= a[0][1]+1 ;
        level_row_thrushold_col.push_back(t) ;

        for(int e=1 ;e<a.size() ;e++){
            int max_level = level_row_thrushold_col.size()+1,min=0 , mid ;

            while(max_level-min>1){
                mid = (max_level+min)/2 ;
                // cout<< mid<<" ";
                if(check(mid-1,level_row_thrushold_col,a[e]))min = mid ;
                else max_level = mid ;
            }
            if(level_row_thrushold_col.size()==min){
                map<int,int> tr ; tr[a[e][0]+1]= a[e][1]+1 ;
                level_row_thrushold_col.push_back(tr) ;
            }
            else {
                if(level_row_thrushold_col[min].find(a[e][0]+1)==level_row_thrushold_col[min].end())level_row_thrushold_col[min][a[e][0]+1] = a[e][1]+1 ;
                else level_row_thrushold_col[min][a[e][0]+1] = mini(level_row_thrushold_col[min][a[e][0]+1],a[e][1]+1) ;
            }
        }

        return level_row_thrushold_col.size() ;
    }
    int maxEnvelopes(vector<vector<int>>& a) {
        sort(a.begin() ,a.end()) ;
        int ans =solve(a) ;
        return ans;
    }
};
118490