#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/binary-search/example-capacity-to-ship-packages

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/binary-search/example-capacity-to-ship-packages

Repovive

Example - Capacity to Ship Packages - Binary Search | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Example - Capacity to Ship Packages

Another binary search on the answer problem.

Problem: Ship packages over $D$ days. Find minimum capacity.

Approach: Binary search on capacity $[\max(weights), \sum(weights)]$ . For each capacity, simulate loading and count days.

function shipWithinDays(weights, D):
    low = max(weights)
    high = sum(weights)
    while low < high:
        mid = (low + high) / 2
        if canShip(weights, mid, D):
            high = mid
        else:
            low = mid + 1
    return low

Time: $O(n \log(\sum weights))$ . Space: $O(1)$ .