Minimum Throughput to Drain the Queue

A queue holds `tasks` in order, where tasks[i] is the work units of the i-th task. Each shift can do at most C units of work and processes tasks in order (a task is never split across shifts). Return the minimum capacity C so that all tasks finish within `shifts` shifts.

Examples

in: tasks = [1, 2, 3, 4, 5], shifts = 3

out: 6

[1,2,3] [4] [5] all fit under 6

in: tasks = [10], shifts = 1

out: 10

one task needs at least its own size

Constraints

1 <= len(tasks) <= 10^5
1 <= tasks[i] <= 10^4
1 <= shifts <= len(tasks)

Hints

target: O(n log(sum)) time⌘↩ run · ⇧⌘↩ submit