题目

在 D 天内送达包裹的能力

思路

搜索区间为$[left, right]$，初始$left=max(weights)$，$right=sum(weights)$

  • 能运送完，下一搜索区间$[left, mid-1]$
  • 不能送完，下一搜索区间$[mid+1, right]$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:

        def can_finish(w):
            cnt = 0
            temp = 0
            for weight in weights:
                temp += weight
                if temp > w:
                    temp = weight
                    cnt += 1
            if temp:
                cnt += 1
            return cnt <= days

        left = max(weights)
        right = sum(weights)

        while left <= right:
            mid = left + (right - left) // 2
            if can_finish(mid):
                right = mid - 1
            else:
                left = mid + 1
        return left