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