Capacity To Ship Packages Within D Days

1. Calculate the lower and upper bounds for the ship's capacity. The lower bound (min_capacity) is the weight of the heaviest package. The upper bound (max_capacity) is the sum of all package weights. 2. Iterate through each possible capacity c from min_capacity to max_capacity. 3. For each capacity c, check if it's possible to ship all packages within days. 3a. To check, simulate the process: Initialize days_needed = 1 and current_load = 0. 3b. Iterate through the weights array. For each weight, try to add it to the current_load. 3c. If current_load + weight <= c, update current_load += weight. 3d. If current_load + weight > c, a new day is required. Increment days_needed and set current_load = weight. 4. If the calculated days_needed is less than or equal to the given days, then the current capacity c is a valid solution. Since we are iterating from the smallest possible capacity, this is the minimum capacity. Return c.

The core idea is to iterate through all potential capacities and test each one. The search for the capacity starts from the weight of the heaviest package (since the ship must be able to hold at least that much) and goes up to the total weight of all packages (a guaranteed upper bound). For each candidate capacity, we simulate the shipping process to determine how many days it would take. We do this by greedily loading packages for a day until the next package exceeds the current day's capacity, at which point we move to the next day. If the total days required for a given capacity is within the allowed days, we have found our answer, as we are checking capacities in increasing order.

1java class Solution { private boolean canShip(int[] weights, int days, int capacity) { int daysNeeded = 1; int currentWeight = 0; for (int weight : weights) { if (weight > capacity) return false; if (currentWeight + weight > capacity) { daysNeeded++; currentWeight = weight; } else { currentWeight += weight; } } return daysNeeded <= days; } public int shipWithinDays(int[] weights, int days) { int maxWeight = 0; int totalWeight = 0; for (int weight : weights) { maxWeight = Math.max(maxWeight, weight); totalWeight += weight; } for (int capacity = maxWeight; capacity <= totalWeight; capacity++) { if (canShip(weights, days, capacity)) { return capacity; } } return totalWeight; } } 

1. Define the search range for the capacity. The lower bound low is the maximum individual package weight. The upper bound high is the total weight of all packages. 2. Initialize a variable ans to store the minimum feasible capacity, initially set to high. 3. While low <= high: 3a. Calculate the middle capacity: mid = low + (high - low) / 2. 3b. Check if this mid capacity is feasible using a helper function. The helper function simulates the shipping process greedily and returns true if the number of days required is at most days. 3c. If mid is a feasible capacity: this could be our answer, but we want the minimum. So, we store it (ans = mid) and try to find a smaller capacity by setting high = mid - 1. 3d. If mid is not a feasible capacity: it's too small. We need a larger capacity, so we set low = mid + 1. 4. After the loop terminates, ans (or low depending on implementation) will hold the minimum capacity required.

We first establish a search space for the capacity. The minimum possible capacity is the weight of the heaviest package (max(weights)), and a safe maximum is the sum of all weights (sum(weights)). We then apply binary search within this range [max(weights), sum(weights)]. In each step of the binary search, we pick a candidate capacity mid. We then check if it's feasible to ship all packages within days with this capacity. This feasibility check is done by a helper function that greedily simulates the loading process in O(N) time. If the mid capacity is feasible (i.e., requires days or fewer), it means we might be able to do even better with a smaller capacity. So, we record mid as a potential answer and try searching in the lower half of the range: high = mid - 1. If the mid capacity is not feasible, it's too small. We must increase the capacity, so we search in the upper half: low = mid + 1. This process continues until the search space is exhausted (low > high), at which point we will have found the smallest capacity that works.

1java class Solution { private boolean isFeasible(int[] weights, int days, int capacity) { int daysNeeded = 1; int currentWeight = 0; for (int weight : weights) { if (currentWeight + weight > capacity) { daysNeeded++; currentWeight = weight; } else { currentWeight += weight; } } return daysNeeded <= days; } public int shipWithinDays(int[] weights, int days) { int low = 0; int high = 0; for (int weight : weights) { low = Math.max(low, weight); high += weight; } int minCapacity = high; while (low <= high) { int mid = low + (high - low) / 2; if (isFeasible(weights, days, mid)) { minCapacity = mid; high = mid - 1; } else { low = mid + 1; } } return minCapacity; } }