NINJA'S TRUCK

Easy
0/40
0 upvote
Asked in companies
AmazonYamaha Motor India

Problem statement

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 is the number of boxes of type I.
unitsperBox is the number of units in each box of type I.
And an integer ‘K’ denoting the limit of boxes on the truck.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
3 3
1 1
2 5
1 3
2 1
2 5
3 4

Sample Output 1:

13
5

Explanation for sample input 1:

Test Case 1:
As the limit on boxes is ‘3’ so we choose ‘2’ boxes each of ‘5’ units and ‘1’ boxes of ‘3’ units making our maximum number of units in the required number of boxes that is ‘13’.

Test Case 2:
As the limit on boxes is ‘1’ so we can choose only one box so we choose ‘1’ box containing ‘5’ units making our maximum number of units in the required number of boxes that is ‘5’.

Sample Input 2:

1
4 4
3 5
2 10
1 15
2 4

Sample Output 2:

40

Explanation for sample input 2:

Test Case 1:
As the limit on boxes is ‘4’ so we choose ‘1’ box of ‘15’ units and ‘2’ box of ‘10’ units each and ‘1’ box of ‘5’ unit making our maximum number of units in the required number of boxes that is ‘40’.
Hint

Can you think of using a 1-D array for storing each box weight?

Approaches (4)
Brute Approach

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.

  • 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’.
Time Complexity

O(N * log(N) ), where ‘N’ represents the total number of boxes present in the given ‘BOX’ array.

 

As we are sorting our array which takes O(N * log(N) ) all other loops will cost us time complexity as O(N) so overall complexity becomes O(N * log(N) ).

Space Complexity

O(N ), where ‘N’ represents the total number of boxes present in the given ‘BOX’ array.

 

As we are using a 1-D array which takes space equal to no of boxes in each row present in the given ‘BOX’ array.

Code Solution
(100% EXP penalty)
NINJA'S TRUCK
Full screen
Console