Last Updated: 10 Apr, 2021
NINJAS TRUCK
Easy
Asked in companies
Ninja is assigned a task to deliver some boxes which contain different units having different weights. With the help of his truck, he will earn money on the basis of the number of units of boxes he will deliver by his truck. Ninja truck has some capacity on the number of boxes he can put on his truck.
So your task is to find a way so that ninja will choose boxes in a way that units will be maximum and he would be able to get more money you will be provided with an array of ‘BOX’, where BOX[i] = [countofBoxes, unitsperBox].
CountofBoxes represents the number of boxes of the same type i.e containing the units of the same value.
UnitsperBox represents the number of units in the box or we simply say that unit value.
And an integer ‘K’ denoting the limit of boxes on the truck.
Input Format :
The first line of input contains a ‘T’ number of test cases.
The first line of each test case contains an integer ‘N’ and ‘K’ denoting the number of rows in array ‘BOX’ and the limit on boxes on the truck. Then, ‘N’ lines follow.
Each line contains two space-separated integers denoting the row values i.e count of boxes and units per box.
Output Format :
For each test case, print a single line containing the maximum number of units that Ninja can deliver.
The output of each test case will be printed in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
1 <= N <= 1000
1 <= BOX[i] <= 1000
1 <= K <= 10 ^ 6
Where ‘T’ is the number of test cases, ‘N’ is the number of rows in 2-D array ‘BOX’, and ‘K’ is the limit on boxes on the truck.
Time Limit: 1 sec
Approaches
The idea here is to store all boxes units separately in a 1-D array and now from that array, we can easily find the maximum value which can be formed using boxes satisfying given condition on the box.
Algorithm:
- Firstly we count the total number of boxes present in the ‘Box’ array and declare a 1-D array of that size and also declare a variable ‘ans’ initialize it from ‘0’.
- Now we fill our 1-D array with the value of units containing in one box.
- For ex- Given Box array is { { 2, 2 }, { 3, 1 } } so our 1-D array would look like {2, 2, 1, 1, 1 }
- Now we simply sort our array from greater to smaller elements.
- Now simply run a loop up to ‘K’ and store the sum of the array in the ‘ans’ variable.
- Return the ‘ans’.
The idea here is to optimize the space and time complexity for which we can think of sorting in the given 2-D array on the basis of the value of unitsperBox which helps in optimizing space as well as time as now we don’t consider a box of the same type as different.
Algorithm:
- Firstly we sort our given 2-D array on the basis of the value of unit weight.
- Now we can simply traverse our 2-D array and try to find out the maximum units we can load on a truck and in every iteration, we check whether we can pick more boxes of that type according to ‘K’.
- We declare an ‘ans’ variable and store the sum of the weight of units in it
- if we can pick that box.
- Else we break the loop.
- Now we simply return the ‘ans’.