Capacity to Ship Packages Within D Days - Binary Search / Advanced

Problems
21

from typing import List

def min_max_weight(weights: List[int], d: int) → int:
# WRITE YOUR BRILLIANT CODE HERE
required_days = d
left, right = max(weights), sum(weights)

while left < right:
    total_days, cur_sum_weights = 1, 0
    mid = (left + right) // 2
    for w in weights:
        if cur_sum_weights + w > mid:
            total_days += 1
            cur_sum_weights = 0
        cur_sum_weights += w
    if total_days > required_days:
        left = mid + 1
    else:
        right = mid
return left
22

Much better description of the problem mentioned in https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

23

My feedback for this team is also to hire a proof-reader/editor for a lot of these questions.

24

const feasible2=(weights, maxWeight, d) => {
let reqDays = 1;
let load = 0;
let i = 0;
const n = weights.length;
while (i < n) {
if ( load + weights[i] <= maxWeight) {
load += weights[i];
i += 1;
} else {
reqDays += 1;
load=0;
}
}

return reqDays <= d;

}

const minMaxWeight=(w,d)=>{

let max=w.reduce( (a,b)=> a+b);

let min = Math.max( Math.max (…w) , Math.floor ( max/d ) );

let boundry=0,m=0;

while(min <= max) {

m=Math.floor( (min+max) / 2 );

if( feasible2 (w,m,d) ){
  boundry=m;
  right=m-1;
}

else 
  left=m+1;

}

return boundry;

}
it shortens the range by a bit by comparing max element in the weight array with sum of elements divided by no. of days,
as the ans is always be greater or equal to by sum of elements divided by no.of days

25

a little mistake in th source code updated code

const feasible2=(weights, maxWeight, d) => {
let reqDays = 1;
let load = 0;
let i = 0;
const n = weights.length;
while (i < n) {
if ( load + weights[i] <= maxWeight) {
load += weights[i];
i += 1;
} else {
reqDays += 1;
load=0;
}
}

return reqDays <= d;

}

const minMaxWeight=(w,d)=>{

let max=w.reduce( (a,b)=> a+b);

let min = Math.max( Math.max (…w) , Math.floor ( max/d ) );

let boundry=0,m=0;

while(min <= max) {

m=Math.floor( (min+max) / 2 );

if( feasible2 (w,m,d) ){
  boundry=m;
  max=m-1;
}

else 
  min=m+1;

}

return boundry;

}
it shortens the range by a bit by comparing max element in the weight array with sum of elements divided by no. of days, as the ans is always be greater or equal to by sum of elements divided by no.of days

26

I have no idea how you guys are deriving the maximum weight from this…

27

Can you be more specific which part you don’t understand?

28

The truck has to be able to carry every package including the one with the maximum weight. That’s why the minimum has to be max(weights).

29

The truck has to be able to carry every package including the one with the maximum weight. That’s why the minimum has to be max(weights).

30

I feel that this is more of a dynamic programming problem?

31

Very confusing explanation. I’m still not clear about it :frowning:

32

What is the time complexity for this?

33

@mod: I am not able to see the solutions that I had written in the Try it yourself section.
I was able to see all of my solutions written in Try it yourself , but now it has disappeared.
Please let me know how to fix this ?

34

I would love to see a discussion of the Space/Time Complexity of the proposed solution.
Can you please add it?

35

I believe the time complexity of this would be O(n log n). O(log n) for the binary search and O(n) for the helper function. Space complexity should be O(1) or O(n) if the array is counted. Could be wrong on this though.

36

the correct answer should be 11

weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
d = 5
1+10, 2+9, 3+8, 4+7, 5+6

37

The packages must be delivered in the order in which they appear within the list. Not any random order which is what your solution proposes.

38

good point. I was confused as well. Thank you for explaining.

39

I think this question would benefit a bit from a little more explanation. I checked out the problem on another platform and was able to understand a bit easier.

40

Agreed. If anyone is looking for a good explanation - https://www.youtube.com/watch?v=4lK5pdSXhCk