I think its supposed to say at minimum the capacity is max(weights) not sum(weights)
This is incorrect: “At minimum, if our truck capacity is only 1 package, we need the sum(weights) days to ship all packages.”
It should be something like this: “At minimum, if our truck capacity is only 1 package, we need the max(weights) days to ship all packages.”
Thank you for pointing out! We’ve fix this.
Weird, I am still seeing sum(weights) instead of max(weights). The sentence is right under the “Solution” heading.
The diagram currently shows “1-55 days”, and “feasible(days)” which is also incorrect. It should say “capacity” instead of days since 1-55 is the possible capacity (given weights 1-10). Optional: use max(weights) instead of 1 as the start of the range in the diagram.
Is the overall runtime O(NlogN), where N is the size of weights? We do logN searches, where each search checks feasible(weight) in O(N) time.
Or is the runtime O(log(N^2)*N) because the possible range of weights to verify can expand to N^2 (N weights each with value N)?
Small type for the Python solution code, for def feasible() return type hint should be bool, I believe.
It would be interesting always explain the time complexity of the solution because this is very important in an interview. Thanks.
I think it should be “capacity” instead of “days” in the diagram
Feasible logic is wrong. Try following custom input:
1 1 1 2 2 2
3
Your out put will be 4 size truck.
But 3 size truck is smallest feasible.
2+1, 2+1, 2+1.
Optimal solution for feasible:
For each day:
Binary search max weight that can fit from available weights.
Loop above till binary search till it can’t find element that can fit.
You are required to deliver them in order.
My solution, the process of identifying the pattern and target search space is quite interesting.
def min_max_weight(weights: List[int], d: int) → int:
# WRITE YOUR BRILLIANT CODE HERE
min_cap = max(weights)
max_cap = sum(weights)
search_space = [i for i in range(min_cap, max_cap + 1)]
# print(f"min: {min_cap}, max: {max_cap}, space: {search_space}")
l, r, res = 0, len(search_space) - 1, 0
# TC = M * log N where M is the size of the search space and N is the
# number of items
# SC = M
while l <= r:
m = (l + r) // 2
days = 0
total = 0
for w in weights:
if total + w < search_space[m]:
total += w
elif total + w == search_space[m]:
days += 1
total = 0
else:
days += 1
total = w
if total > 0:
days += 1
if days <= d:
r = m - 1
res = search_space[m]
else:
l = m + 1
return res
Found an error in the solution description:
Old: At minimum, if our truck capacity is only 1 package, we need the max(weights) days to ship all packages.
New: At minimum, if our truck capacity is only 1 package, we need capacity equal to max(weights) to ship all packages.
So would the run time be O(n log n)?
I think the solution wording At minimum, if our truck capacity is only 1 package, we need the max(weights) days to ship all packages. is confusing and may actually be misleading/ incorrect. Wouldn’t it be better to say something along the lines of The capacity of the truck should be at least equal to the package having the maximum weight, that is max(weights).
Looks like there is a typo here or I am not understanding something “At minimum, if our truck capacity is only 1 package, we need the max(weights) days to ship all packages.”. Should “max(weights)” not be “len(weights)”?
It’s the maximum value of weights.
It’s poorly worded. I thought the same thing.