leetcode medium : Capacity To Ship Packages Within D days

https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

Capacity To Ship Packages Within D Days - LeetCode

 

class Solution:
    def shipWithinDays(self, weights, D):
        left, right = max(weights), sum(weights)
        while left < right:
            mid, need, cur = (left + right) // 2, 1, 0
            for w in weights:
                if cur + w > mid:
                    need += 1
                    cur = 0
                cur += w
            if need > D: left = mid + 1
            else: right = mid
        return left

하루에 옮길 수 있는 양을 고정시켜놓고 가능한지 불가능한지 검사한다.

이걸로 이진 탐색을 하면 된다.

하루에 옮길 수 있는 양은 최소 max(weights)여야 하고 최대 sum(weights)까지 가능하다.

가능 여부를 조사하는데 O(N)이 걸리고 이진 탐색을 하는데에 O(log N)이 걸리므로 곱하면 O(N log N)