Optimal Task Distribution to Minimize Maximum Workload

You are given a sequence of tasks, where each task requires a certain number of hours to complete. There are k employees available to perform these tasks. Tasks must be assigned in the given order and cannot be split between employees. Your goal is to determine the minimum possible value of the maximum workload among all employees when tasks are assigned optimally.

Formally, let \(tasks = [t_1, t_2, \dots, t_n]\) be an array of positive integers representing the hours required for each task, and let \(k\) be the number of employees. You need to partition the array into \(k\) or fewer contiguous segments such that the largest sum over all segments is minimized. This largest segment sum is the answer.

The optimal solution can be found via a binary search approach combined with a greedy check to verify if a given maximum workload is feasible.

inputFormat

The input is read from standard input and consists of two lines:

• The first line contains two space-separated integers \(n\) and \(k\), where \(n\) is the number of tasks and \(k\) is the number of employees.
• The second line contains \(n\) space-separated integers detailing the number of hours each task requires.

outputFormat

Output a single integer to standard output representing the minimum possible maximum workload among the employees after optimally distributing the tasks.

7 3
10 7 8 12 6 8 7

21