Last Updated: 14 Apr, 2021

Ninja and Locker

Moderate

Asked in company

Solve now

Problem statement

Ninja has two arrays ‘CASH’’ and ‘LOCKER’ denoting the height of each stack of cash of unit width and height of ‘N’ sections in the locker respectively.

The locker sections are labeled from 0 to ‘N’ - 1 from left to right.

Cash stacks can only be put in the locker by following the certain rules:

Cash stacks can’t be piled up

You can take any order of cash stack

You can push the stack in the locker only from left to right

If height of some stack is greater than the height of locker section then the stack will be stopped before that room

Ninja wants your help to find the maximum number of cash stacks he can put into the locker.

For Example:

As we can see from the example below we are only able to put two stacks in the locker so our answer will be 2.

Input Format:

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’ denoting the size of ‘CASH’ and ‘LOCKER’ arrays respectively.

The second line of each test case contains ‘N’ space-separated integers denoting the elements of ‘CASH’. 

The third line of each test case contains ‘M’ space-separated integers denoting the elements of ‘LOCKER’.

Output Format:

For each test case, print the maximum number of cash stacks that ninja can put in the locker.

The output of each test case will be printed in a separate line.

Constraints:

1 <= T <= 5
1 <= N,M <= 5000
1 <= CASH[i], LOCKER[i] <= 10^9

Where ‘T’ is the number of test cases, ‘N’ and ‘M’ is the size of ‘CASH’ and ‘LOCKER’ respectively, and 'CASH[i]' and 'LOCKER[i]' denotes the 'i-th' elements of the array.

Time limit: 1 sec

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

The idea here is to put the smallest possible cash stack in the locker first and if no stack is available then we check the next section.

To implement this we first need to make a valid locker ‘VALIDLOCKER’ in which if VALIDLOCKER[i] < VALIDLOCKER[i+1], then the maximum height of section VALIDLOCKER[i+1] is VALIDLOCKER[i].

After this we will iterate ‘LOCKER’ section one by one and find the minimum possible cash stack to put in this section.

Algorithm:

Declare array ‘VALIDLOCKER’ and ‘PLACED’ initialise to 0.
Declare a variable ‘ANS’ := 0
for( i: 0 - > LOCKER.size )
- VALIDLOCKER[i] = minimum of VALIDLOCKER[i-1] and LOCKER[i]
for ( i : VALIDLOCKER.size -1 -> 0 )
- Declare a variable ‘MAXCASH’ = VALIDLOCKER[i]
- Find the minimum cash and assign its value to ‘MAXCASH’ and make ‘PLACED[i]’ = 1.
- If we are unable to find a cash stack then continue else increment ‘ANS’.
return ‘ANS’

Solve now

02 Approach

The idea here is to use greedy technique, that is we will first put the smallest stack in the locker and if all stack size are greater than the size of the locker section then return the ans.

To implement this we first need to make a valid locker ‘VALIDLOCKER’ in which if VALIDLOCKER[i] < VALIDLOCKER[i+1], then the maximum height of section VALIDLOCKER[i+1] is VALIDLOCKER[i].

After this we will sort the CASH array and check till when we can insert the cash stack in the VALIDLOCKER.

Algorithm:

Declare an array ‘VALIDLOCKER’.
for( i: 0 - > LOCKER.size )
- VALIDLOCKER[i] = minimum of VALIDLOCKER[i-1] and LOCKER[i]
sort( CASH )
Declare ‘C’ := 0 , ‘L’ := LOCKER.Size - 1 and ‘ANS’ := 0.
Repeat the below steps until ‘C’ < CASH.size and ‘L’ > -1
- if (CASH[C] <= LOCKER[L]
  - C++ , L-- and ANS++
- else
  - L--
return ANS.

Solve now