Ship Cargo in 5 Days

#Google #Medium #BinarySearch

Question

Suppose we have n cargos in a queue that we want to ship from one location to another location. Find the minimum ship capacity we need to deliver all cargos in 5 days

Explanation Video

Explain how to approach the question and coding explanation as well.

Solution

Use a custom binary search algorithm to find the minimum capacity that is capable of shipping all cargoes in 5 days.

int findMinimumCapacity(int[] weights) {
    // Keep track of the range of remaining capacities to try out. 
    int left = 0;
    int right = Arrays.stream(weights).sum();

    // Keep track of the minimum capacity found so far.
    int minimumCapacity = -1;
    
    // Binary search loop to find the mimimum capacity. 
    while (right - left > 1) {
        // Typical binary search algorithm: find the midpoint. 
        int capacity = (right + left) / 2;
        if (shipInFiveDays(weights, capacity)) {
            // Case 1. Shipping all cargoes in 5 days possible with the
            // given capacity: discard the right side of possibilities.
            right = capacity;
            minimumCapacity = capacity;
        } else {
            // Case 2. Cannot ship all cargoes with the given capacity:
            // discard the left side of possibilities.
            left = capacity;
        }
    }

    return minimumCapacity;
}

// Returns true if it is possible to ship all the given weights 
// with the given capacity in 5 days. 
private boolean shipInFiveDays(int[] weights, int capacity) {
    int currentSum = 0;
    int count = 0;
    for (int weight : weights) {
        // If a cargo is heavier than the given capacity, we
        // cannot ship this specific cargo at all.
        if (weight > capacity) {
            return false;
        }

        // No more space to add an additional cargo.
        if (currentSum + weight > capacity) {
            count++;
            currentSum = 0;
        }

        currentSum += weight;
    }

    // Last cargo has not been counted in the while loop so plus 1.
    return count + 1 <= 5;
}