Capacity to Ship packages within D days { koko Vairant }

XXX. Ship Packages Within D Days

Binary Search

Greedy

Problem Statement:

Given an array weights representing the weights of packages and an integer D representing the number of days, find the minimum weight capacity of a ship required to ship all packages within D days. Each day, the ship can carry a contiguous segment of packages, but it cannot exceed its weight capacity.

Algorithm:

This problem is solved using binary search combined with a greedy approach:

1. Find the search range for the ship's capacity:
   • Minimum capacity: The weight of the heaviest package (since each package must be shipped individually).
   • Maximum capacity: The sum of all package weights (if shipped in one day).
2. Perform binary search on the capacity range:
• For a midpoint capacity, check if it is possible to ship all packages within D days.
• If possible, try a smaller capacity; otherwise, increase the capacity.
3. To check feasibility for a given capacity, use a greedy approach to calculate the required number of days by iterating through the weights and summing them until the capacity is exceeded.

Complexity:

Time Complexity: O(n log(sum(weights) - max(weights))), where n is the number of weights. The binary search requires O(log(max - min)) steps, and each feasibility check is O(n).
Space Complexity: O(1), as no additional data structures are used.

Java Implementation:

public class Solution {

    public int shipWithinDays(int[] weights, int D) {
        int min = 0;
        int max = 0;

        // Calculate the initial search range
        for (int w : weights) {
            max += w;
            min = Math.max(min, w);
        }

        int capacity = Integer.MAX_VALUE;

        // Perform binary search
        while (min <= max) {
            int mid = min + (max - min) / 2;

            if (possible(weights, D, mid)) {
                capacity = mid; // Update capacity if feasible
                max = mid - 1; // Try smaller capacity
            } else {
                min = mid + 1; // Increase capacity
            }
        }

        return capacity;
    }

    // Check if it's possible to ship within D days with given capacity
    public boolean possible(int[] weights, int D, int capacity) {
        int days = 1;
        int total = 0;

        for (int weight : weights) {
            if (total + weight <= capacity) {
                total += weight; // Add weight to the current day
            } else {
                days++; // Start a new day
                total = weight; // Reset total to the current package

                if (days > D) return false; // Exceeded allowed days
            }
        }

        return true;
    }
}