Leetcode 1011. Capacity To Ship Packages Within D Days

Problem

Leetcode 1011 - Capacity To Ship Packages Within D Days

Example:

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10


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


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

Approach

We can use binary search to solve this problem, where left = max(weights), so every day we can carry weight, and right = sum(weights), so within one day we can carry all the weights

We can then calculate our days and limit by looping through the list

• if limit + w > mid
  • increase day
  • reset limit
• limit + w

Finally we can update left or right pointer depending on the result of day

• if day <= days
  • update result
  • right = mid-1
• else
  • left = mid+1

Visualization of the Approach:

weights = [1,2,3,4,5,6,7,8,9,10], days = 5
left = 10, right = 55, mid = 32
day 1 = (1,2,3,4,5,6,7)
day 2 = (8,9,10)
Since day <= days, res = 32, right = 31

left = 10, right = 31, mid = 20
day 1 = (1,2,3,4,5)
day 2 = (6,7)
day 3 = (8,9)
day 4 = (10)
Since day <= days, res = 20, right = 19

left = 10, right = 19, mid = 14
day 1 = (1,2,3,4)
day 2 = (5,6)
day 3 = (7)
day 4 = (8)
day 5 = (9)
day 6 = (10)
Since day > days, left = 15

left = 15, right = 19, mid = 17
day 1 = (1,2,3,4,5)
day 2 = (6,7)
day 3 = (8,9)
day 4 = (10)
Since day <= days, res = 17, right = 16

left = 15, right = 16, mid = 15
day 1 = (1,2,3,4,5)
day 2 = (6,7)
day 3 = (8)
day 4 = (9)
day 5 = (10)
Since day <= days, res = 15, right = 14

Since left > right, return res

res = 15

Here is the Python code for the solution:

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        # the minimum weight should be max of weights, so every day we can carry weight
        # the maximum weight should be whole sum, so every weight should be able to carried in one day
        left, right = max(weights), sum(weights)
        res = 0

        while left <= right:
            mid = (left + right) // 2

            limit = 0
            day = 0
            for w in weihgts:
                if limit + w > mid:
                    day += 1
                    limit = 0
                limit += w
            day += 1

            if day <= days:
                res = mid
                right = mid-1
            else:
                left = mid+1
        
        return res    

Time Complexity and Space Complexity

Time Complexity: $O(n log n)$

Space Complexity: $O(1)$