Minimum Ship Capacity to Deliver Ordered Packages Within a Day Limit
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A line of packages waits at a dock, and a ship must carry all of them to their destination. The ship makes one trip per day and has a fixed weight capacity. Packages must be loaded in the order they stand in the line.
Given the weights of the packages in line order and the number of days available, return the smallest capacity that lets the ship deliver every package within that many days.
### Function Signature
```python
def min_ship_capacity(weights: list[int], days: int) -> int:
```
`weights[i]` is the weight of the `i`-th package in line order. `days` is the number of days available.
### Rules
- Each day the ship carries a contiguous run of packages that starts with the first package not yet shipped. Packages cannot be split, skipped or reordered.
- The total weight carried on one day must not exceed the capacity.
- All packages must be delivered within `days` days. Finishing in fewer days is allowed.
- The capacity is a positive integer. Return the smallest capacity for which delivery within `days` days is possible.
### Constraints
- `1 <= len(weights) <= 10^5`
- `1 <= weights[i] <= 10^4`
- `1 <= days <= len(weights)`
- The total weight is at most `10^9`, so the answer fits in a signed 32-bit integer.
### Examples
**Example 1**
```text
Input: weights = [4, 8, 2, 5, 7, 3, 6], days = 3
Output: 14
```
With capacity 14 the ship can carry `[4, 8, 2]`, then `[5, 7]`, then `[3, 6]`, which weigh 14, 12 and 9. Capacity 13 is not enough: the first day can carry at most `[4, 8]`, because adding the 2 makes 14, and carrying less on the first day only leaves more for the other two. The remaining `[2, 5, 7, 3, 6]` cannot be split into two contiguous runs of weight at most 13: `[2]` leaves 21, `[2, 5]` leaves `[7, 3, 6]` = 16, and `[2, 5, 7]` already weighs 14.
**Example 2**
```text
Input: weights = [9, 1, 1, 1], days = 2
Output: 9
```
The package of weight 9 must fit on some day, so no capacity below 9 works. Capacity 9 works: `[9]`, then `[1, 1, 1]`.
**Example 3**
```text
Input: weights = [5, 2, 6], days = 1
Output: 13
```
Everything must go on a single trip, so the capacity must be at least 5 + 2 + 6 = 13.
Overview: Given package weights in a fixed loading order and a number of days, find the smallest ship capacity that delivers every package within that many days, carrying one contiguous run of packages per day. It tests reasoning precisely about feasibility, choosing correct bounds and handling large inputs efficiently.
Read the full Microsoft Software Engineer interview experience this question came from
A line of packages waits at a dock, and a ship must carry all of them to their destination. The ship makes one trip per day and has a fixed weight capacity. Packages must be loaded in the order they stand in the line.
Implement `min_ship_capacity(weights, days)`. `weights[i]` is the weight of the `i`-th package in line order, and `days` is the number of days available. Return the smallest capacity that lets the ship deliver every package within `days` days.
**Rules**
- Each day the ship carries a contiguous run of packages that starts with the first package not yet shipped. Packages cannot be split, skipped or reordered.
- The total weight carried on one day must not exceed the capacity.
- All packages must be delivered within `days` days. Finishing in fewer days is allowed.
- The capacity is a positive integer. Return the smallest capacity for which delivery within `days` days is possible.
**Constraints**
- `1 <= len(weights) <= 10^5`
- `1 <= weights[i] <= 10^4`
- `1 <= days <= len(weights)`
- The total weight is at most `10^9`, so the answer fits in a signed 32-bit integer. No input or output value exceeds `2^31 - 1`.
**Example 1**
```
Input: weights = [4, 8, 2, 5, 7, 3, 6], days = 3
Output: 14
```
With capacity 14 the ship can carry `[4, 8, 2]`, then `[5, 7]`, then `[3, 6]`, which weigh 14, 12 and 9. Capacity 13 is not enough: the first day can carry at most `[4, 8]`, and the remaining `[2, 5, 7, 3, 6]` cannot be split into two contiguous runs that each weigh at most 13.
**Example 2**
```
Input: weights = [9, 1, 1, 1], days = 2
Output: 9
```
The package of weight 9 must fit on some day, so no capacity below 9 works. Capacity 9 works: `[9]`, then `[1, 1, 1]`.
Constraints
- 1 <= len(weights) <= 10^5
- 1 <= weights[i] <= 10^4
- 1 <= days <= len(weights)
- The total weight sum(weights) is at most 10^9, so the answer fits in a signed 32-bit integer (no value exceeds 2^31 - 1)
Examples
Input: ([4, 8, 2, 5, 7, 3, 6], 3)
Expected Output: 14
Explanation: Source example 1: [4, 8, 2] | [5, 7] | [3, 6] with loads 14, 12 and 9; the first day's load equals the capacity exactly, and capacity 13 needs 4 days.
Input: ([9, 1, 1, 1], 2)
Expected Output: 9
Explanation: Source example 2: the heavy package forces capacity 9; [9] | [1, 1, 1].
Hints
- The heaviest package must ride on some day, and the whole line fits in one trip when the capacity equals the total weight, so the answer lies between those two values.
- Finishing in fewer than days days is allowed, so for a given capacity it is enough to know the fewest days that capacity needs.
- A day's load may equal the capacity exactly: in Example 1, [4, 8, 2] weighs 14 and fits capacity 14.