動機

  1. method call的代價會不會太高!?
  2. 見到bsearch的範圍的重要性

Problem

A conveyor belt has packages that must be shipped from one port to another within days days.

The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

 

Example 1:

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5Output: 15Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:1st day: 1, 2, 3, 4, 52nd day: 6, 73rd day: 84th day: 95th day: 10Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

Example 2:

Input: weights = [3,2,2,4,1,4], days = 3Output: 6Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:1st day: 3, 22nd day: 2, 43rd day: 1, 4

Example 3:

Input: weights = [1,2,3,1,1], days = 4Output: 3Explanation:1st day: 12nd day: 23rd day: 34th day: 1, 1

 

Constraints:

  • 1 <= days <= weights.length <= 5 * 104
  • 1 <= weights[i] <= 500

Sol1

用二分去猜，要裝多少

但這個解很慢，1948 ms

後面就是慢慢優化的過程

class Solution:
    def fill(self,mid):
        tmp = 0
        lastIndex = 1
        ss = 0
        for w in self.ws:
            if w > mid:
                return [self.D+1, 0] # force enlarge
            ss = max(ss,tmp)
            if tmp + w > mid:
                tmp = w
                lastIndex += 1
            elif tmp + w == mid:
                #print("HERE",mid,ss)
                ss = max(ss,mid)
                tmp = 0
                lastIndex += 1
            else:
                tmp += w
                #print("HERE",ss,tmp)
            ss = max(ss,tmp)
        #print("final",ss)
        return [lastIndex, ss]
    def shipWithinDays(self, ws: List[int], D: int) -> int:
        self.ws = ws
        self.D = D
        i = min(sum(ws)//D,max(ws))
        j = (sum(ws))+1
        limit = 0
        while i < j:
            mid = i + (j-i)//2
            print(mid)
            lastIdx, limit = self.fill(mid)
            if lastIdx == D:
                j = mid
            elif lastIdx < D:
                j = mid
            else:
                i = mid+1
        return self.fill(i)[1]

Sol2 簡化加總

原本是加總後分成三個case，看小於、等於、大於上限 之後就看每個case的加總之後是要設定成多少

不過可以在加新重量之前，就看會不會超過就好

1080 ms

class Solution:
    def fill(self,mid):
        tmp = 0
        lastIndex = 1
        ss = 0
        for w in self.ws:
            if tmp + w > mid:
                lastIndex += 1
                tmp = 0
            tmp += w
            ss = max(ss,tmp)
        return [lastIndex, ss]
    def shipWithinDays(self, ws: List[int], D: int) -> int:
        self.ws = ws
        self.D = D
        i = 1
        j = (sum(ws))+1
        limit = 0
        while i < j:
            mid = i + (j-i)//2
            #print(mid)
            lastIdx, limit = self.fill(mid)
            if lastIdx == D:
                j = mid
            elif lastIdx < D:
                j = mid
            else:
                i = mid+1
        return self.fill(i)[1]

Sol3: 縮小範圍

考慮到 D 等於 weights 長度的case，這會發生什麼事?

[407,59,416,189,326,109,399,404,181,275,135,57,147,7,158,201,218,111,56,9,149,231,186,293,187,395,75,100,334,23,327,434]
32

每一次加總都會小於或等於D，這樣bsearch會出事，算出來的答案會一直降下去!! 這樣算出來的答案不會是容量，導致要另外紀錄目前加出來的的最大值(fill的ss)

所以要把範圍縮小，最小至少要是所有重量的最大值，讓容量不會無下限的往下，這樣就可以直接把bsearch到的東西直接丟回去

976 ms

class Solution:
    def fill(self,mid):
        tmp = 0
        lastIndex = 1
        ss = 0
        for w in self.ws:
            if tmp + w > mid:
                lastIndex += 1
                tmp = 0
            tmp += w
            ss = max(ss,tmp)
        return [lastIndex, ss]
    def shipWithinDays(self, ws: List[int], D: int) -> int:
        self.ws = ws
        self.D = D
        j = (sum(ws))
        i = max(ws)
        
        limit = 0
        while i < j:
            mid = i + (j-i)//2
            #print(mid)
            lastIdx, limit = self.fill(mid)
            if lastIdx == D:
                j = mid
            elif lastIdx < D:
                j = mid
            else:
                i = mid+1
        return i

Sol4: remove method call

還是很慢，如果把method call去掉的話

560 ms

class Solution:
    def shipWithinDays(self, ws: List[int], D: int) -> int:
        j = sum(ws)
        i = max(j//D, max(ws))
        limit = 0
        while i < j:
            mid = i + (j-i)//2
            tmp = 0
            lastIndex = 1
            #print(mid)
            for w in ws:
                if tmp + w > mid:
                    lastIndex += 1
                    tmp = 0
                tmp += w
            if lastIndex <= D:
                j = mid
            else:
                i = mid+1
        return i

Sol Final: 再縮小範圍

從Sol3，我們知道 最小至少要是所有重量的最大值

那最大值應該是多少?

  • 總重量平均?
    • 會太小，像是 [1,2,3,4,5,6,7,8,9,10], 5 就直接死亡
  • 總重量?
    • 太大了，所以前面的解才都那麼慢

平均會太小是因為有一些重量特別小，導致平均變小，所以可以 把每一個貨物當成最重的重量，去算平均

class Solution:
    def shipWithinDays(self, ws: List[int], D: int) -> int:
        i = max(ws)
        j = len(ws)*i //D + 1
        limit = 0
        while i < j:
            mid = i + (j-i)//2
            tmp = 0
            lastIndex = 1
            for w in ws:
                if tmp + w > mid:
                    lastIndex += 1
                    tmp = 0
                tmp += w
            if lastIndex <= D:
                j = mid
            else:
                i = mid+1
        return i