1011. Capacity To Ship Packages Within D Days

MediumView on LeetCode

Array Binary Search

Intuition

Binary search on ship capacity. Min = max weight, Max = total weight. Check if capacity allows shipping in D days.

Algorithm

1lo=max(weights), hi=sum(weights).
2Feasibility: greedily pack each day. If days <= D, feasible.
3Find minimum feasible capacity.

Example Walkthrough

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

1.lo=10, hi=55. Binary search finds 15.

Output: 15

Common Pitfalls

•Must ship in order. lo must be at least max(weights) to fit any single package.

1011.cs

// Approach: Binary search on capacity between max(weights) and sum(weights); greedily count days needed for a given capacity.
// Time: O(n log(sum)) Space: O(1)

public class Solution {
    public int ShipWithinDays(int[] weights, int days) {
        int maxEle = Int32.MinValue;
        int sumofW = 0;
        for(int i = 0; i < weights.Length; i++)
        {
            maxEle = Math.Max(maxEle, weights[i]);
            sumofW += weights[i];
        }

        int low = maxEle, high = sumofW;
        int ans = -1;
        while(low <= high)
        {
            int mid = (low + high) / 2;
            int daysRequired = GetDaysRequired(weights, mid);
            if(daysRequired <= days)
            {
                ans = mid;
                high = mid - 1;
            }
            else
                low = mid + 1;
        }

        return ans;
    }

    private int GetDaysRequired(int[] weights, int capacity)
    {
        int days = 1, load = 0;
        for(int i = 0; i < weights.Length; i++)
        {
            load += weights[i];
            if(load > capacity)
            {
                load = weights[i];
                days++;
            }
        }

        return days;
    }
}

1011.go

import "math"

func shipWithinDays(weights []int, days int) int {
    maxEle := math.MinInt32;
    var sumOfW int

    for i := 0; i < len(weights); i++ {
        if maxEle < weights[i] {
            maxEle = weights[i]
        }
        sumOfW += weights[i]
    }

    low := maxEle
    high := sumOfW
    ans := -1
    
    for low <= high {
        mid := (low + high) / 2
        daysRequired := getDaysRequired(weights, mid)

        if(daysRequired <= days) {
            ans = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }

    return ans
}

func getDaysRequired(weights []int, capacity int) int {
    days := 1
    var load int

    for i := 0; i < len(weights); i++ {
        load += weights[i]
        if(load > capacity) {
            load = weights[i]
            days++
        }
    }

    return days
}

Was this solution helpful?