390. Fair Split of Work
A manager has a line of tasks, where nums[i] is the number of hours the i-th task takes. She will hand the line to k workers by cutting it into k consecutive, non-empty groups, so every task goes to exactly one worker and the order of tasks is kept inside each group.
Each worker's workload is the sum of the hours in the group. Return the smallest possible value of the largest workload, taken over all ways to cut the line into k groups. An approach that tries every way to cut the line is far too slow; look for something that is fast for hundreds of thousands of tasks.
Example 1
- Input:
- nums = [8,3,6,9,2], k = 2
- Output:
- 17
- Explanation:
Splitting as [8, 3, 6] and [9, 2] gives workloads 17 and 11, so the largest is 17; the split [8, 3] and [6, 9, 2] gives 11 and 17. No split does better than 17.
Example 2
- Input:
- nums = [4,4,4], k = 3
- Output:
- 4
- Explanation:
Each worker gets one task, so the largest workload is 4.
Constraints
1 ≤ nums.length ≤ 105
0 ≤ nums[i] ≤ 1000
1 ≤ k ≤ min(50, nums.length)
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log S), where S is the total hours
- Space
- O(1)