Delivering Boxes from Storage to Ports

Moderate
0/80
Average time to solve is 15m
0 upvote
Asked in company
Amazon

Problem statement

You have the task of delivering some boxes from storage to their ports using only one ship. However, this ship has a limit on the number of boxes and the total weight that it can carry. You are given an array boxes, where boxes[i] = [ports​​i​, weighti], and three integers portsCount, maxBoxes, and maxWeight.

- ports​​i is the port where you need to deliver the ith box and weightsi is the weight of the ith box.
- portsCount is the number of ports.
- maxBoxes and maxWeight are the respective box and weight limits of the ship.

The boxes need to be delivered in the order they are given. The ship will follow these steps:

- The ship will take some number of boxes from the boxes queue, not violating the maxBoxes and maxWeight constraints.
- For each loaded box in order, the ship will make a trip to the port the box needs to be delivered to and deliver it. If the ship is already at the correct port, no trip is needed, and the box can immediately be delivered.
- The ship must end at storage after all the boxes have been delivered.

Return the minimum number of trips the ship needs to make to deliver all boxes to their respective ports.

Note: 
Remember that the given list of boxes is to be delivered in the given order in the original box list.
For Example: 
Input: boxes = [[1, 1], [2, 1], [1, 1]], portsCount = 2, maxBoxes = 3, maxWeight = 3
Output: 4

Explanation: The optimal strategy is as follows: 

The ship takes all the boxes in the queue, goes to port 1, then port 2, then port 1 again, then returns to storage. 4 trips.
So the total number of trips is 4.

Note that the first and third boxes cannot be delivered together because the boxes need to be delivered in order (i.e. the second box needs to be delivered at port 2 before the third box).
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input is the number of test cases ‘T’ which are going to be there.

The first line of each test case would be three space-separated integers representing the ‘portsCount’, ‘maxBoxes’, and ‘maxWeight’.

The second line of each test case would an integer ‘N’ denoting the total number of boxes given which are needed to be delivered.

Now each ‘N’ line of the test case would comprise of two space-separated integers ‘port[i]’ and ‘weight[i]’.
Output Format: 
For each test case, print a single line containing a single integer denoting the minimum number of trips the ship needs to make to deliver all boxes to their respective ports.

The output for every test case will be printed in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of. Just implement the function.
Constraint : 
1 <= T <= 5
1 <= boxes.length <= 10 ^ 5
1 <= portsCount, maxBoxes, maxWeight <= 10 ^ 5
1 <= ports​​i <= portsCount
1 <= weightsi <= maxWeight

Where ‘boxes’ is the 2-D array of [‘portsi’,’ weights’], ‘portsCount’ is the number of ports, maxBoxes, and maxWeight is the respective box and weight limits of the ship.

Time Limit: 1 sec
Sample Input 1:
2
3 3 6
5
1 2
3 3
3 1
3 1
2 4
5 5 7
9
2 4
2 5
3 1
3 2
3 7
3 1
4 4
1 3
5 2
Sample output 1:
6
14
Explanation:
The optimal strategy is as follows: 
- The ship takes the first box, goes to port 1, then returns to storage. 2 trips.
- The ship takes the second, third and fourth boxes, goes to port 3, then returns to storage. 2 trips.
- The ship takes the fifth box, goes to port 3, then returns to storage. 2 trips.
So the total number of trips is 2 + 2 + 2 = 6.

Hence the Output: 6


The optimal strategy is as follows:
- The ship takes the first box, goes to port 2, then storage. 2 trips.
- The ship takes the second box, goes to port 2, then storage. 2 trips.
- The ship takes the third and fourth boxes, goes to port 3, then storage. 2 trips.
- The ship takes the fifth box, goes to port 3, then storage. 2 trips.
- The ship takes the sixth and seventh boxes, goes to port 3, then port 4, then storage. 3 trips. 
- The ship takes the eighth and ninth boxes, goes to port 1, then port 5, then storage. 3 trips.
So the total number of trips is 2 + 2 + 2 + 2 + 3 + 3 = 14.

Hence the Output: 14
Sample Input 2:
3 6 7
6
1 4
1 2
2 1
2 1
3 2
3 4
Sample output 2:
6
Hint

You can use a naive dp approach and try to further optimize upon it.

Approaches (1)
Delivering Boxes from Storage to Ports

The main idea here is to know that this is one typical structure of dynamic programming. We iterate through every box as if it's the last box, and calculate the minimal cost of shipping all of them. In each iteration, cost of the last trip is certain (depend on the type of the end division of it), so we just need to find the minimal cost of previous trips while the last trip is still within limiation.

 

The algorithm will be-

  1. Initialise a dp list (array) for keeping track of the different trip counts and which would store the minimum amounts of trips which we are going to require.
  2. We also initialise the ‘trips’ with 2 (since we would atleast require a trip to go to the starting port and come back to the storage always), size of holded (selected) number of boxes in each trip ‘boxes_selected’, w: weight in hold initialised by 0, left: end position for the last split initialised by -1, right: end position in hold initialised by 0.
  3. Now we keep iterating along the given length of the boxes which are to be selected tracked using the right pointer that we initialised.
  4. For each right value of the box that we have selected we will keep checking the following:
    1. split trip when have to, but always only hold minimun boxes that do not escalate our trip count.
    2. on spliting, if the splitted 2 are different ports, we can save one trip that is holding (eg. 2 boxes needed to go to 2 ports so the holded trips is 3, but after splitting from the first box, for the holded portion, we only need to go to 1 port which takes 2 trips)
  5. Now we keep increasing the weights ‘w’ and the ‘boxes_selected’ count with the boxes which we have already selected and counted the trips for. Also for different ports keep on increasing value of trips by 1 (eg. only 1 port in hold needs 2 trips, but 2 ports need 3) and update dp[right] = dp[left] + trips
  6. We finally return the minimum number of trips the ship needs to make to deliver all boxes to their respective port i.e. dp[-2]
Time Complexity

O(N), where ‘N’ is the total number of boxes required to be delivered. 

 

Since, for each box, we traverse the list of boxes and keep selecting the minimum number of trips giving combinations of boxes in each iteration, hence, the time complexity grows by O(N).

Space Complexity

O(N), where ‘N’ is the total number of boxes required to be delivered. 

 

We are using a dp list (array) to store the minimized number of trips for each box selection and splits hence, the Space Complexity is O(N).

Code Solution
(100% EXP penalty)
Delivering Boxes from Storage to Ports
Full screen
Console