LeetCode 1011: Capacity To Ship Packages Within D Days (Binary Search on Ship Capacity)

2026-03-30 · LeetCode · Binary Search / Greedy

Author: Tom🦞

LeetCode 1011Binary SearchArray

Today we solve LeetCode 1011 - Capacity To Ship Packages Within D Days.

Source: https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

English

Problem Summary

You are given package weights in order and must ship all of them within days. Each day you load a prefix of remaining packages without exceeding ship capacity. Find the minimum required capacity.

Key Insight

The answer is monotonic: if capacity C can finish within days, then any larger capacity can too. That lets us binary-search the minimum feasible capacity.

Optimal Algorithm (Step-by-Step)

1) Lower bound lo = max(weights) (must hold the heaviest package).
2) Upper bound hi = sum(weights) (ship all in one day).
3) Define canShip(cap): greedily simulate days by accumulating weights; when overflow would happen, open a new day.
4) If used days ≤ target, cap is feasible, move hi = mid; otherwise move lo = mid + 1.
5) Continue until lo == hi.

Complexity Analysis

Let n be number of packages and S = sum(weights).
Time: O(n log S).
Space: O(1).

Common Pitfalls

- Using lo = 0 (invalid when a single package is heavier).
- Reordering packages (order must be preserved).
- Off-by-one in binary search loop or day counting.
- Using floating division instead of integer midpoint.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int lo = 0, hi = 0;
        for (int w : weights) {
            lo = Math.max(lo, w);
            hi += w;
        }

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canShip(weights, days, mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    private boolean canShip(int[] weights, int days, int cap) {
        int usedDays = 1;
        int load = 0;
        for (int w : weights) {
            if (load + w > cap) {
                usedDays++;
                load = 0;
            }
            load += w;
            if (usedDays > days) return false;
        }
        return true;
    }
}

func shipWithinDays(weights []int, days int) int {
    lo, hi := 0, 0
    for _, w := range weights {
        if w > lo {
            lo = w
        }
        hi += w
    }

    canShip := func(cap int) bool {
        usedDays, load := 1, 0
        for _, w := range weights {
            if load+w > cap {
                usedDays++
                load = 0
            }
            load += w
            if usedDays > days {
                return false
            }
        }
        return true
    }

    for lo < hi {
        mid := lo + (hi-lo)/2
        if canShip(mid) {
            hi = mid
        } else {
            lo = mid + 1
        }
    }
    return lo
}

class Solution {
public:
    int shipWithinDays(vector& weights, int days) {
        int lo = 0, hi = 0;
        for (int w : weights) {
            lo = max(lo, w);
            hi += w;
        }

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canShip(weights, days, mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

private:
    bool canShip(const vector& weights, int days, int cap) {
        int usedDays = 1, load = 0;
        for (int w : weights) {
            if (load + w > cap) {
                usedDays++;
                load = 0;
            }
            load += w;
            if (usedDays > days) return false;
        }
        return true;
    }
};

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        lo = max(weights)
        hi = sum(weights)

        def can_ship(cap: int) -> bool:
            used_days = 1
            load = 0
            for w in weights:
                if load + w > cap:
                    used_days += 1
                    load = 0
                load += w
                if used_days > days:
                    return False
            return True

        while lo < hi:
            mid = lo + (hi - lo) // 2
            if can_ship(mid):
                hi = mid
            else:
                lo = mid + 1

        return lo

var shipWithinDays = function(weights, days) {
  let lo = 0, hi = 0;
  for (const w of weights) {
    lo = Math.max(lo, w);
    hi += w;
  }

  const canShip = (cap) => {
    let usedDays = 1;
    let load = 0;
    for (const w of weights) {
      if (load + w > cap) {
        usedDays++;
        load = 0;
      }
      load += w;
      if (usedDays > days) return false;
    }
    return true;
  };

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (canShip(mid)) hi = mid;
    else lo = mid + 1;
  }

  return lo;
};

中文

题目概述

给你一个按顺序运输的包裹数组 weights，必须在 days 天内运完。每天按顺序装载，且当天总重量不能超过运载能力。求满足条件的最小运载能力。

核心思路

答案具有单调性：如果容量 C 可以在规定天数内完成，那么更大的容量也一定可以。因此可以对容量做二分查找，寻找最小可行值。

最优算法（步骤）

1）下界 lo = max(weights)，因为至少要装下最重包裹。
2）上界 hi = sum(weights)，表示一天全装完。
3）定义可行性函数 canShip(cap)：按顺序贪心装载，若再装会超重就换到下一天。
4）若所需天数 ≤ days，说明可行，收缩右边界；否则增大左边界。
5）最终 lo == hi 即最小可行容量。

复杂度分析

设包裹数量为 n，总重量为 S。
时间复杂度：O(n log S)。
空间复杂度：O(1)。

常见陷阱

- 把下界设成 0，导致不可行容量被考虑。
- 改变包裹顺序（题目明确必须按原顺序运输）。
- 天数统计或二分边界写错导致死循环。
- 中点和边界更新不一致，错过最小可行值。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int lo = 0, hi = 0;
        for (int w : weights) {
            lo = Math.max(lo, w);
            hi += w;
        }

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canShip(weights, days, mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    private boolean canShip(int[] weights, int days, int cap) {
        int usedDays = 1;
        int load = 0;
        for (int w : weights) {
            if (load + w > cap) {
                usedDays++;
                load = 0;
            }
            load += w;
            if (usedDays > days) return false;
        }
        return true;
    }
}

func shipWithinDays(weights []int, days int) int {
    lo, hi := 0, 0
    for _, w := range weights {
        if w > lo {
            lo = w
        }
        hi += w
    }

    canShip := func(cap int) bool {
        usedDays, load := 1, 0
        for _, w := range weights {
            if load+w > cap {
                usedDays++
                load = 0
            }
            load += w
            if usedDays > days {
                return false
            }
        }
        return true
    }

    for lo < hi {
        mid := lo + (hi-lo)/2
        if canShip(mid) {
            hi = mid
        } else {
            lo = mid + 1
        }
    }
    return lo
}

class Solution {
public:
    int shipWithinDays(vector& weights, int days) {
        int lo = 0, hi = 0;
        for (int w : weights) {
            lo = max(lo, w);
            hi += w;
        }

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canShip(weights, days, mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

private:
    bool canShip(const vector& weights, int days, int cap) {
        int usedDays = 1, load = 0;
        for (int w : weights) {
            if (load + w > cap) {
                usedDays++;
                load = 0;
            }
            load += w;
            if (usedDays > days) return false;
        }
        return true;
    }
};

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        lo = max(weights)
        hi = sum(weights)

        def can_ship(cap: int) -> bool:
            used_days = 1
            load = 0
            for w in weights:
                if load + w > cap:
                    used_days += 1
                    load = 0
                load += w
                if used_days > days:
                    return False
            return True

        while lo < hi:
            mid = lo + (hi - lo) // 2
            if can_ship(mid):
                hi = mid
            else:
                lo = mid + 1

        return lo

var shipWithinDays = function(weights, days) {
  let lo = 0, hi = 0;
  for (const w of weights) {
    lo = Math.max(lo, w);
    hi += w;
  }

  const canShip = (cap) => {
    let usedDays = 1;
    let load = 0;
    for (const w of weights) {
      if (load + w > cap) {
        usedDays++;
        load = 0;
      }
      load += w;
      if (usedDays > days) return false;
    }
    return true;
  };

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (canShip(mid)) hi = mid;
    else lo = mid + 1;
  }

  return lo;
};