Split into k Shifts, Minimise the Longest Shift

tasks[i] is the duration of task i. The tasks must be done in order and handed to k workers so that each worker gets a contiguous, non-empty block of tasks. A worker's shift length is the sum of their block. Return the smallest possible length of the longest shift.

Examples

Input:  tasks = [7, 2, 5, 10, 8], k = 2
Output: 18
Explanation: [7, 2, 5] and [10, 8] give shifts of 14 and 18.

Input:  tasks = [1, 2, 3, 4, 5], k = 2
Output: 9

Input:  tasks = [1, 4, 4], k = 3
Output: 4

Constraints

• 1 <= k <= len(tasks) <= 3 * 10**4
• 1 <= tasks[i] <= 10**6
• Required time: O(n log(sum(tasks))). Enumerating partitions is hopeless.

Goals

• Reduce an optimisation over partitions to a yes/no question
• Handle the case where k equals the number of tasks