How do I apply binary search in the Capacity To Ship Packages Within D Days problem?

Apply binary search over the possible ship capacities, starting from the maximum weight of a single package and going up to the sum of all weights. At each step, check if it's possible to ship within the given days with the current capacity.

What is the greedy strategy used in this problem?

The greedy strategy involves packing the ship day by day, adding packages to the ship until the total weight exceeds the current capacity. When it does, a new day starts.

What should I watch out for when implementing binary search in this problem?

Ensure the binary search bounds are correctly set and that you handle the logic for checking feasibility efficiently. Avoid off-by-one errors when determining whether a capacity can fit within the allowed days.

How does GhostInterview help with preparing for this problem?

GhostInterview provides targeted practice and hints related to binary search, helping you optimize your solution and understand key problem-solving techniques.

What is the time complexity of the solution?

The time complexity is O(n * log(S)), where n is the number of packages, and S is the sum of all weights. This is due to the binary search and the linear scan required to check feasibility.

#1011

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

在 D 天内送达包裹的能力

传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。传送带上的第 i 个包裹的重量为 weights[i] 。每一天，我们都会按给出重量（ weights ）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。返回能在 days 天内将传送带上的所有包裹送达的船的最低运…

数组二分查找

题目描述

传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。

示例 1：

输入：weights = [1,2,3,4,5,6,7,8,9,10], days = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10

请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。

示例 2：

输入：weights = [3,2,2,4,1,4], days = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4

示例 3：

输入：weights = [1,2,3,1,1], days = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1

提示：

1 <= days <= weights.length <= 5 * 10⁴
1 <= weights[i] <= 500

lightbulb

解题思路

方法一：二分查找

我们注意到，如果运载能力 $x$ 能够在 $days$ 天内运送完所有包裹，那么运载能力 $x + 1$ 也能在 $days$ 天内运送完所有包裹。也即是说，随着运载能力的增加，运送天数只会减少，不会增加。这存在一个单调性，因此我们可以使用二分查找的方法来寻找最小的运载能力。

我们定义二分查找的左边界 $left= \max\limits_{i=0}^{n-1} weights[i]$ ，右边界 $right = \sum\limits_{i=0}^{n-1} weights[i]$ 。然后二分枚举运载能力 $x$ ，判断是否能在 $days$ 天内运送完所有包裹。如果能，那么我们将右边界调整为 $x$ ，否则将左边界调整为 $x + 1$ 。

判断是否能在 $days$ 天内运送完所有包裹的方法是，我们从左到右遍历包裹，将当前包裹加入当前运载能力的船上，如果当前船的运载能力超过了 $x$ ，那么我们将当前包裹放到下一天的船上，同时天数加一。如果天数超过了 $days$ ，那么我们返回 $false$ ，否则返回 $true$ 。

时间复杂度 $O(n \times \log \sum\limits_{i=0}^{n-1} weights[i])$ ，空间复杂度 $O(1)$ 。其中 $n$ 为包裹数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        def check(mx):
            ws, cnt = 0, 1
            for w in weights:
                ws += w
                if ws > mx:
                    cnt += 1
                    ws = w
            return cnt <= days

        left, right = max(weights), sum(weights) + 1
        return left + bisect_left(range(left, right), True, key=check)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates understanding of binary search on the answer space.
question_mark
Candidate uses a greedy strategy to pack the ship while maintaining the required days.
question_mark
Candidate effectively handles the edge cases, like the smallest and largest possible capacities.

warning

常见陷阱

外企场景

error
Failing to correctly implement the binary search bounds, which could lead to an incorrect answer.
error
Misunderstanding the greedy strategy and incorrectly packing packages, resulting in more days than allowed.
error
Overcomplicating the solution or missing optimization opportunities by not using binary search efficiently.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Adjust the problem to allow packages to be loaded in any order, requiring a different optimization approach.
arrow_right_alt
Change the constraints to allow multiple ships to be used, altering the solution's complexity and strategy.
arrow_right_alt
Introduce a variable number of days and see if the approach can handle dynamic adjustments.

help

常见问题

外企场景

继续练习

#1004 最大连续1的个数 III #1027 最长等差数列 #1095 山脉数组中查找目标值