oavoservice Original Explanation: Classic "Binary Search on Answer" problem. The key is to write feasibility as a monotonic function.
Problem (Restated)
You are given orders[i] representing the number of orders the i-th restaurant needs to process. You have d dashers.
Rules:
- Each dasher has a maximum capacity of
k. - A restaurant's orders can be distributed among multiple dashers.
- However, one dasher can only serve one restaurant (cannot serve multiple restaurants).
Find the minimum k such that all orders can be covered by d dashers.
Key Observation: Feasibility Check
If a restaurant has x orders, and each dasher can handle at most k, then the number of dashers needed for this restaurant is:
need = ceil(x / k)
Sum up need for all restaurants. If sum_need <= d, then k is feasible.
As k increases, sum_need monotonically non-increases, so we can use binary search.
Complexity
- Feasibility Check:
O(n) - Binary Search:
O(log max(orders)) - Total:
O(n log max(orders))
Python Reference Implementation
from math import ceil
def min_capacity(orders, d):
if not orders:
return 0
# Lower bound: must be able to handle at least 1 order; tighter bound is max(ceil(x/d)), but 1 or max(orders)//d works
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
Common Interview Questions
- Why is
feasible(k)monotonic? (Larger k means fewer or equal dashers needed per restaurant) - Why is
hi = max(orders)sufficient? (When k equals the max restaurant orders, each restaurant needs at most 1 dasher) - How do you prevent overflow/timeout? (Early exit pruning: return immediately if
total > d)
DoorDash loves to use this type of question to test "Binary Search on Answer" patterns. oavoservice's training focus is: Translate business constraints into ceil formulas, then write feasible instantly.
Need real interview questions? Contact WeChat Coding0201 immediately to get real questions.