# LeetCode 1011: Capacity To Ship Packages Within D Days

## Problem Restatement

We have packages with weights given in an array `weights`.

A ship loads packages in order every day. Once a day's load would exceed the ship's capacity, we stop loading and start a new day.

We are given `days`, the maximum number of days allowed.

We need to return the minimum weight capacity of the ship so that all packages can be shipped within `days` days.

The official constraints state that `1 <= days <= weights.length <= 5 * 10^4` and `1 <= weights[i] <= 500`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `weights` and integer `days` |
| Output | Minimum ship capacity |
| Constraint | Packages must be shipped in order |

Function shape:

```python
def shipWithinDays(weights: list[int], days: int) -> int:
    ...
```

## Examples

Example 1:

```python
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
days = 5
```

With capacity `15`: day 1 gets `[1,2,3,4,5]`, day 2 gets `[6,7]`, day 3 gets `[8]`, day 4 gets `[9]`, day 5 gets `[10]`. Total 5 days. ✓

Answer:

```python
15
```

Example 2:

```python
weights = [3, 2, 2, 4, 1, 4]
days = 3
```

With capacity `6`: day 1 `[3,2]`, day 2 `[2,4]`, day 3 `[1,4]`. All fit in 3 days.

Answer:

```python
6
```

## Key Insight

The minimum possible capacity is `max(weights)` (must fit the heaviest package).

The maximum useful capacity is `sum(weights)` (ship everything in one day).

The answer is monotone: if capacity `c` works, any `c' > c` also works.

This makes binary search on the capacity applicable.

## Algorithm

1. Set `left = max(weights)` and `right = sum(weights)`.
2. While `left < right`:
   - `mid = (left + right) // 2`.
   - Check if capacity `mid` allows shipping within `days` days.
   - If yes, try smaller: `right = mid`.
   - If no, try larger: `left = mid + 1`.
3. Return `left`.

The feasibility check: greedily load packages day by day, counting how many days are needed.

## Correctness

Binary search finds the smallest `mid` for which the feasibility check passes.

The feasibility check is greedy: load as many packages as possible each day without exceeding capacity. This uses the fewest days possible for a given capacity.

If the greedy check says `days` days suffice, the capacity works. If not, we need more capacity.

## Edge Cases

- Check the smallest and largest valid search values; off-by-one errors usually appear at the boundaries.
- Decide whether the predicate is looking for the first true value, the last true value, or an exact match.
- When the target is absent, the loop should still terminate and return the problem-specific failure value.

## Complexity

Let `n = len(weights)` and `S = sum(weights)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log S)` | Binary search over capacity range, `O(n)` check each time |
| Space | `O(1)` | Constant extra space |

## Common Pitfalls

- Do not mix inclusive and half-open bounds inside the same loop.
- Make sure each branch strictly reduces the search interval.

## Implementation

```python
class Solution:
    def shipWithinDays(self, weights: list[int], days: int) -> int:
        def can_ship(capacity: int) -> bool:
            current = 0
            needed_days = 1
            for w in weights:
                if current + w > capacity:
                    needed_days += 1
                    current = 0
                current += w
            return needed_days <= days

        left = max(weights)
        right = sum(weights)

        while left < right:
            mid = (left + right) // 2
            if can_ship(mid):
                right = mid
            else:
                left = mid + 1

        return left
```

## Code Explanation

The feasibility function `can_ship` simulates the loading process:

```python
for w in weights:
    if current + w > capacity:
        needed_days += 1
        current = 0
    current += w
```

Start a new day when the current load would exceed capacity.

Binary search narrows the capacity range:

```python
while left < right:
    mid = (left + right) // 2
    if can_ship(mid):
        right = mid
    else:
        left = mid + 1
```

When `left == right`, we have the minimum capacity.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5) == 15
    assert s.shipWithinDays([3, 2, 2, 4, 1, 4], 3) == 6
    assert s.shipWithinDays([1, 2, 3, 1, 1], 4) == 3
    assert s.shipWithinDays([1], 1) == 1

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| 10 packages, 5 days | `15` | Optimal grouping fits in 5 days |
| 6 packages, 3 days | `6` | Each day gets balanced load |
| 5 packages, 4 days | `3` | Small capacity works |
| 1 package, 1 day | `1` | Minimum case |