Capacity To Ship Packages Within D Days Leetcode Solution

Problem statement

In the problem ” Capacity To Ship Packages Within D Days,” we have packets in port A that must be transferred to port B in D days.

we are given a weights array that contains the weight of each packet and the number of days in which we need to transfer the packets. Our task is to find the minimum load capacity of the ship to be used to transfer packets from port A to port B in D days.

Example

weights = [1,2,3,4,5,6,7,8,9,10], D = 5

15

Explanation: The ship will transfer the packets in the following way:

First-Day : 1,2,3,4,5

Second-Day 2: 6,7

Third-Day 3: 8

Fourth-Day 4: 9

Fifth-Day 5: 10

In this way, the minimum load capacity of the ship should be 15 to transfer all packets in 5 days.

Approach for Capacity To Ship Packages Within D Days Leetcode Solution

The first and the most important thing to solve this problem is to bring out observations. Here are a few observations for our search interval:

1. The load capacity of the ship should be at least equal to the packet having the maximum weight that is max(weights). let’s name it as Start.
2. We can limit the maximum capacity of the ship to the sum of the weight of all the packets that is sum(weights). let’s name it as End.

Now we have our search interval. Suppose the size of the interval is Length and the number of packets is n.  The naive approach could be to check for each value in the interval if that load capacity can transfer the packets successfully in D days and pick the minimum out of them. The time complexity for the naive approach will be Length*n.

We can improve the time complexity by using Binary Search in place of Linear Search.

The time complexity using the Binary Search approach will be log(Length)*n.

Implementation

C++ code for Capacity To Ship Packages Within D Days Leetcode Solution

#include <bits/stdc++.h>
using namespace std; 
    int shipWithinDays(vector<int>& weights, int D) {
        int left = 0, right = 0;
        for (int w: weights) {
            left = max(left, w);
            right += w;
        }
        while (left < right) {
            int mid = (left + right) / 2, requirement = 1, tillnow = 0;
            for (int w: weights) {
                if (tillnow + w > mid) {
                   requirement += 1;
                   tillnow = 0;
                }
                tillnow += w;
            }
            if (requirement > D) left = mid + 1;
            else right = mid;
        }
        return left;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4,5,6,7,8,9,10}; 
 int d=5;                               

 cout<<shipWithinDays(arr,d)<<endl;
 return 0;
}

15

Java code for Capacity To Ship Packages Within D Days Leetcode Solution

public class Tutorialcup {
    public static int shipWithinDays(int[] weights, int D) {
        int left = 0, right = 0;
        for (int w: weights) {
            left = Math.max(left, w);
            right += w;
        }
        while (left < right) {
            int mid = (left + right) / 2, requirement = 1, tillnow = 0;
            for (int w: weights) {
                if (tillnow + w > mid) {
                   requirement += 1;
                   tillnow = 0;
                }
                tillnow += w;
            }
            if (requirement > D) left = mid + 1;
            else right = mid;
        }
        return left;
    }
  public static void main(String[] args) {
    int [] arr = {1,2,3,4,5,6,7,8,9,10}; 
     int d=5; 
    int ans= shipWithinDays(arr,d);
    System.out.println(ans);
  }
}

15

Complexity Analysis of Capacity To Ship Packages Within D Days Leetcode Solution

Time complexity

The time complexity of the above code is O(n*log(Length)) because we are traversing the weight array log(Length) times. Here n and Length are the numbers of packets and size of the search interval respectively.

Space complexity

The space complexity of the above code is O(1) because we are using only a variable to store the answer.

References