DoorDash VO 面试题：Dasher 最小负载容量（Binary Search + 贪心可行性检查）

# DoorDash VO 面试题：Dasher 最小负载容量（Binary Search + 贪心可行性检查）

oavoservice 原创讲解：典型“二分答案”题，关键是把可行性写成单调函数。

题目（改写版）

给你 orders[i] 表示第 i 家餐厅需要处理的订单量。你有 d 个 dasher。

规则：

• 每个 dasher 的最大处理量是 k。
• 一个餐厅的订单可以分配给多个 dasher。
• 但一个 dasher 只能服务一个餐厅（不能跨餐厅接单）。

问最小的 k 是多少，使得所有订单都能被 d 个 dasher 覆盖。

关键观察：可行性检查

如果某个餐厅订单量为 x，每个 dasher 最多处理 k，那么该餐厅需要的 dashers 数量：

need = ceil(x / k)

把所有餐厅的 need 相加，若 sum_need <= d，则 k 可行。

随着 k 增大，sum_need 单调不增，所以可以二分。

复杂度

• 可行性检查：O(n)
• 二分：O(log max(orders))
• 总计：O(n log max(orders))

Python 参考实现

from math import ceil


def min_capacity(orders, d):
    if not orders:
        return 0

    # 下界：至少要能处理某个餐厅的 1 个订单；更紧的下界是 max(ceil(x/d)) 但这里用 1 或 max(orders)//d 也行
    lo, hi = 1, max(orders)

    def feasible(k):
        total = 0
        for x in orders:
            total += (x + k - 1) // k  # ceil
            if total > d:
                return False
        return True

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

    return lo

面试官常问

• 为什么 feasible(k) 单调？（k 越大，单餐厅需要 dashers 越少或不变）
• 为什么 hi = max(orders) 足够？（k 等于最大餐厅订单量时，每家餐厅最多 1 个 dasher）
• 你如何防止溢出/超时？（提前剪枝：total > d 立刻返回）

DoorDash 这类题非常喜欢用来考“二分答案”套路。oavoservice 的训练重点是：把业务约束翻译成 ceil 公式，然后秒写 feasible。

需要面试真题？ 立刻联系微信 Coding0201，获得真题。