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

Problems
41

Weights must be sorted?

42

No, quote from the question:
“You are required to deliver them in order…”

43

Thanks for the link, I was looking for some better understanding of this!

44

reduce the time with a little extra space…

    int totalWeight =0;
    List<Integer> sumOfWeight = new ArrayList<Integer>();
    sumOfWeight.add(weights.get(0));
    for(int i=1;i<=weights.size()-1;i++){
        totalWeight=totalWeight+weights.get(i);
        sumOfWeight.add(weights.get(i)+sumOfWeight.get(i-1));
    }
    
    totalWeight = totalWeight+weights.get(0);
    
    int minWeightPerDay = totalWeight/d;
    
    int truckCapacity=0;
     int left=0;
    int right=sumOfWeight.size()-1;
    
    while(left<right){
        int mid=(left+right)/2;
        if(sumOfWeight.get(mid)<minWeightPerDay){
            left=mid+1;
            truckCapacity=sumOfWeight.get(left);
        }else if(sumOfWeight.get(mid) > minWeightPerDay){
            right=mid;
            truckCapacity=sumOfWeight.get(right);
        }else{
            if(totalWeight%d==0){
                truckCapacity=sumOfWeight.get(mid);
            }else{
                truckCapacity=sumOfWeight.get(mid)+1;
            }
            
            break;
        }
    }
    return truckCapacity;
45

Guys… cmon… the solution assumes that the weight array is sorted, but the problem doesn’t mention it. With unsorted array, this isn’t solvable in nlogn. Cost me a couple hours. Please fix the problem.

46

nevermind… Got if finally. :man_facepalming:t3: Nice problem.

47

@mod

Can we get a better explanation the feasibility function? I’m very confused on how you should go about determining what weight correlates to the number of days.

48

in feasible function, you can think of capacity as current truck capacity, the loop reduced the capacity by subtracting it with the current package. If the truck does not fit anymore, it do req_days + 1 and resetting the truck capacity (continuing the delivery the next day).

At the end of the loop, we can see how many day it required to transport it with the 2nd argument, and convert it to boolean by doing req_days < d

49

@mb Mine in a different way.

go though the array and each time check to see if you added the new weight in the array would go over the weight your checking. If this is the case then you need to increment the day total and the set the running total to new weight and carry on. Once complete the check the result is lower or equal to the target number of days. IE T in boundary array. The NumberOfDays rreturns the same result as Feasible just alittle easier to follow.
Hope this helps.

public static bool NumberOfDays(int truckSize, List weights, int d) {

    var numOfDays = 1;
    var runningTotal = 0;
    for(var i = 0; i < weights.Count; i++) {                     
        if(runningTotal + weights[i] > truckSize){
           numOfDays++;
           runningTotal = weights[i];
        } else {
           runningTotal += weights[i];
        }        
    }        
    return numOfDays <= d;        
}
50

For those who are struggling, the problem explicitly states that you have to deliver the packages in order, which means, in the contrary, you must not sort the weights.

51

I think the time complexity should be something like O(n log k) because while n is the number of elements of weights array, k is dependent on the value of weights array. @mod can you clarify if this reasoning is correct ?

52

What is the intuition behind this problem? This is just a problem description and a solution.

53

Can we please simplify the problem, explanation and solution here? Not able to understand this.