Optimal Order Liquidation Daily Capacity

A portfolio risk team at Two Sigma must liquidate an inventory of $N$ order packages, specified by size array weights, over exactly $d$ consecutive trading days. The packages must be executed in the exact sequential order given.

Each day, the execution algorithm can liquidate packages up to a maximum daily capacity $C$. Once adding the next package would exceed capacity $C$, trading for that day ceases and the remaining packages carry over to the next day.

Your Task

Implement ship_within_days(weights: list[int], d: int) -> int that determines the least daily capacity $C$ necessary to liquidate all packages within $d$ days in $\mathcal{O}(N \log(\sum weights))$ time.

Constraints

• $1 \le d \le \text{len}(weights) \le 5 \times 10^4$
• $1 \le weights[i] \le 10^5$

Examples

weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
d = 5
# Minimum capacity is 15:
# Day 1: 1, 2, 3, 4, 5 (sum 15)
# Day 2: 6, 7 (sum 13)
# Day 3: 8 (sum 8)
# Day 4: 9 (sum 9)
# Day 5: 10 (sum 10)
# Output: 15