|
| 1 | +#!/usr/bin/python3 |
| 2 | +""" |
| 3 | +A conveyor belt has packages that must be shipped from one port to another |
| 4 | +within D days. |
| 5 | +
|
| 6 | +The i-th package on the conveyor belt has a weight of weights[i]. Each day, we |
| 7 | +load the ship with packages on the conveyor belt (in the order given by |
| 8 | +weights). We may not load more weight than the maximum weight capacity of the |
| 9 | +ship. |
| 10 | +
|
| 11 | +Return the least weight capacity of the ship that will result in all the |
| 12 | +packages on the conveyor belt being shipped within D days. |
| 13 | +
|
| 14 | +Example 1: |
| 15 | +
|
| 16 | +Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5 |
| 17 | +Output: 15 |
| 18 | +Explanation: |
| 19 | +A ship capacity of 15 is the minimum to ship all the packages in 5 days like |
| 20 | +this: |
| 21 | +1st day: 1, 2, 3, 4, 5 |
| 22 | +2nd day: 6, 7 |
| 23 | +3rd day: 8 |
| 24 | +4th day: 9 |
| 25 | +5th day: 10 |
| 26 | +
|
| 27 | +Note that the cargo must be shipped in the order given, so using a ship of |
| 28 | +capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), |
| 29 | +(8), (9), (10) is not allowed. |
| 30 | +Example 2: |
| 31 | +
|
| 32 | +Input: weights = [3,2,2,4,1,4], D = 3 |
| 33 | +Output: 6 |
| 34 | +Explanation: |
| 35 | +A ship capacity of 6 is the minimum to ship all the packages in 3 days like |
| 36 | +this: |
| 37 | +1st day: 3, 2 |
| 38 | +2nd day: 2, 4 |
| 39 | +3rd day: 1, 4 |
| 40 | +Example 3: |
| 41 | +
|
| 42 | +Input: weights = [1,2,3,1,1], D = 4 |
| 43 | +Output: 3 |
| 44 | +Explanation: |
| 45 | +1st day: 1 |
| 46 | +2nd day: 2 |
| 47 | +3rd day: 3 |
| 48 | +4th day: 1, 1 |
| 49 | +
|
| 50 | +Note: |
| 51 | +
|
| 52 | +1 <= D <= weights.length <= 50000 |
| 53 | +1 <= weights[i] <= 500 |
| 54 | +""" |
| 55 | +fromtyingimportList |
| 56 | + |
| 57 | + |
| 58 | +classSolution: |
| 59 | +defshipWithinDays(self,weights:List[int],D:int)->int: |
| 60 | +""" |
| 61 | + Must respect conveyor's order |
| 62 | +
|
| 63 | + Binary search on value range (max, sum) |
| 64 | + """ |
| 65 | +lo=max(weights) |
| 66 | +hi=sum(weights) |
| 67 | +whilelo<hi: |
| 68 | +mid= (lo+hi)//2 |
| 69 | +cnt=1 |
| 70 | +cur=0 |
| 71 | +forwinweights: |
| 72 | +cur+=w |
| 73 | +ifcur>mid: |
| 74 | +cnt+=1 |
| 75 | +cur=w |
| 76 | + |
| 77 | +ifcnt>D: |
| 78 | +lo=mid+1 |
| 79 | +else: |
| 80 | +hi=mid |
| 81 | + |
| 82 | +returnlo |