Question
Envelope Nesting Challenge
In a small town, there is a unique tradition where beautifully crafted envelopes of different sizes are used to pass secret messages.
Each envelope has a specific width and height, and they can be stacked inside one another, just like Russian dolls, but only if both the width and height of one envelope are larger than the other.
Nitin, fascinated by this tradition, wants to know the maximum number of envelopes he can fit inside one another without rotating them.
Can you help Nitin figure out the maximum number of envelopes that can be nested together?
Input
The first line of the input contains a two space separated integers m and n, representing the size(rows and columns) of the 2D array "envelopes".
The next m line of the input contains n integers representing elements of 2D array "envelopes".
Constraints
1 ≤ envelopes.length ≤ 103
envelopes[i].length == 2
1 ≤ wi, hi ≤ 105
The next m line of the input contains n integers representing elements of 2D array "envelopes".
Constraints
1 ≤ envelopes.length ≤ 103
envelopes[i].length == 2
1 ≤ wi, hi ≤ 105
Output
Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).
Example
Sample Input
4 2
5 4
6 4
6 7
2 3
Sample Output
3
Explanation
The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
4 2
5 4
6 4
6 7
2 3
Sample Output
3
Explanation
The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).