<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>

// Hay
void printArr(const vector<int> & arr){
    for(int i = 0 ; i < arr.size() ; i ++) cout<<arr[i]<<" ";
    cout<<endl;
}
void printArr(const vector<vector<int>> & arr){
    for(int i = 0 ; i < arr.size() ; i ++) printArr(arr[i]);
}
bool myfunc(const vector<int> & a, const vector<int> & b){
    if(a[0] == b[0]) return a[1] > b[1];
    return a[0] < b[0];
}
int BinarySearch(const vector<int> & arr, int val){
    int idx = -1, l = 0, r = arr.size() - 1;
    while(l <= r){
        int m = l + (r - l) / 2;
        if(arr[m] < val){
            idx = m;
            l = m + 1;
        }else r = m - 1;
    }
    return idx;
}
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& arr) {
        sort(arr.begin(), arr.end(), myfunc);
        //printArr(arr);
        int i;
        unordered_set<int> s;
        for(i = 0 ; i < arr.size() ; i ++) s.insert(arr[i][1]);
        vector<int> dp(s.size() + 1, INT_MAX);
        dp[0] = INT_MIN;
        for(i = 0 ; i < arr.size() ; i ++){
            //cout<<"i: "<<i<<" "<<arr[i][1]<<endl;
            //cout<<"dp: "; printArr(dp);
            int idx = BinarySearch(dp, arr[i][1]);
            dp[idx + 1] = min(dp[idx + 1], arr[i][1]);
        }
        int ans = 0;
        for(i = 1 ; i < dp.size() ; i ++) if(dp[i] != INT_MAX) ans = i;
        return ans;
    }
};
92896