# 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，获得真题。
联系方式
Email: [email protected] Telegram: @OAVOProxy