Rotation of envelope is not allowed, that is, height and width can’t be exchanged
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next 3*T lines represent the ‘T’ test cases.
The first line of each test case contains an integer ‘N’, representing the number of envelopes.
The second line of the test case contains ‘N’ space-separated integers representing elements of the array ‘height’.
The third line of the test case contains ‘N’ space-separated integers representing elements of the array ‘width’.
For each test case, print, in a separate line, the maximum number of envelopes you can Russian doll.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 50
1 <= n <= 10^4
1 <= height[i] <= 10^9
1 <= width[i] <= 10^9
Time Limit: 2 sec
Sort all the envelopes according to their height in non-decreasing order and if the height of envelopes is the same then arrange them in non-increasing order of their width. The maximum number of envelopes you can Russian doll will now be the length of the Longest Increasing Subsequence of widths.
This is because after sorting all heights will increase, so we only need to consider widths.
Note, we arrange width in decreasing order when the height is the same, this prevents Longest increasing subsequence algorithm, to include more than one envelope with the same height.
For example if there are 4 envelopes [2,3], [4,6], [3,7], [4,8] in [height, width] manner.
Then after sorting by height we get, [2, 3], [3, 7], [4, 8], [4, 6].
Now, we only consider the widths. The order of widths will be the one obtained after sorting by height. The maximum number of envelopes you can Russian Doll is the length of the longest increasing subsequence of [3, 7, 8, 6] that is 3.
We can implement it as follows.
As explained in the previous approach this problem will reduce to finding the Longest Increasing Subsequence. We can also find the Longest Increasing Subsequence in O(N * log(N)) using dynamic programming and binary search as explained here.
We can implement it as follows.
Return length of the longest increasing subsequence of array ‘arr’. We can find it efficiently using dynamic programming and binary search as explained here.
Ninja And The Strictly Increasing Array
Negative To The End
8-Queen Problem
Day 28 : Fake Coin Problem
Find Duplicate in Array