HardAlgorithms & Data StructuresBuild

Split Video Jobs Across Workers

You're scheduling video-encoding jobs across a fixed pool of workers. Jobs must be assigned in order (a worker takes a *contiguous* run of jobs from the queue). Each worker processes its run sequentially, so a worker's...

Start problem Browse all problems

What you will practice

PythonArrays & StringsBinary SearchGreedySearch on AnswerOptimization

Requirements

Return an integer — the minimum value of `max(bucket_sum)` over all ways to split `jobs` into exactly `k` non-empty contiguous buckets.
Jobs must stay in their original order — buckets are contiguous slices, not arbitrary subsets.
Raise `ValueError` if `k <= 0` or `k > len(jobs)`.
If `jobs` is empty (and `k` is also 0), return 0.
When `k == 1`, the answer is `sum(jobs)`.
When `k == len(jobs)`, the answer is `max(jobs)`.
Run in O(n log(sum(jobs))) — the perf test will TLE an exponential partition search.

Starter files

main.pyEditable starter

What the judge checks

Runs in the python environment with the python-pytest runner.
Uses a 8000ms judge budget.
Behavior rules include: Correct On Simple Partitions, Handles K Equals One And K Equals N, Handles Single Oversized Job, Performance On Large Input Under Limit.

Constraints

Do not modify the inputs.
Use only the standard library.
An O(2^n) brute-force partition search will time out on 200k jobs.

Example behavior

Input

jobs = [10, 20, 30, 40, 50], k = 2

Output

Best split: [10, 20, 30] | [40, 50]. Bucket sums are 60 and 90; max is 90.

Input

jobs = [7, 2, 5, 10, 8], k = 2

Output

Split [7, 2, 5] | [10, 8] → sums 14 and 18. Max is 18.

Follow-up

If jobs could be reordered freely, would the answer change? What problem does that turn into, and is it still tractable?