Loading problem...
You are given an array of positive integers representing task durations and an integer k representing the number of workers available. Your goal is to divide all tasks among exactly k workers such that each worker receives a contiguous segment of tasks (tasks must be processed in order), and the maximum total workload assigned to any single worker is minimized.
Each worker must be assigned at least one task, and every task must be assigned to exactly one worker. The tasks cannot be reordered—each worker receives a consecutive block of tasks from the original sequence.
Return the smallest possible value of the maximum workload that any worker has to handle when the tasks are optimally distributed.
This is a classic optimization problem that requires finding the fairest distribution of sequential work across multiple workers, ensuring no single worker is disproportionately burdened.
nums = [7,2,5,10,8]
k = 218There are multiple ways to partition the tasks into 2 contiguous groups. The optimal split is [7,2,5] and [10,8]. The first worker handles tasks summing to 14, and the second handles 18. The maximum workload is 18, which is the minimum achievable across all possible partitions.
nums = [1,2,3,4,5]
k = 29The optimal partitioning is [1,2,3] and [4,5]. Worker 1 has workload 6, worker 2 has workload 9. The maximum workload of 9 is the smallest possible for any valid two-way partition.
nums = [1,4,4]
k = 34With 3 workers and 3 tasks, each worker receives exactly one task: [1], [4], and [4]. The maximum workload is 4 (shared by two workers), which is the minimum possible since no partitioning can reduce the workload of handling the largest individual task.
Constraints