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 total time is the sum of its assigned jobs' durations.
Given the job durations and the number of workers k, return the minimum possible value of max(worker_total_time) — i.e. the fastest the whole batch can finish if you partition optimally.
The judge runs your solution against a 200,000-job batch. An exponential partition search will TLE. The intended approach is binary search on the answer space.
- Return an integer — the minimum value of
max(bucket_sum)over all ways to splitjobsinto exactlyknon-empty contiguous buckets. - Jobs must stay in their original order — buckets are contiguous slices, not arbitrary subsets.
- Raise
ValueErrorifk <= 0ork > len(jobs). - If
jobsis empty (andkis also 0), return 0. - When
k == 1, the answer issum(jobs). - When
k == len(jobs), the answer ismax(jobs). - Run in O(n log(sum(jobs))) — the perf test will TLE an exponential partition search.
jobs = [10, 20, 30, 40, 50], k = 2
90
Best split: [10, 20, 30] | [40, 50]. Bucket sums are 60 and 90; max is 90.
jobs = [7, 2, 5, 10, 8], k = 2
18
Split [7, 2, 5] | [10, 8] → sums 14 and 18. Max is 18.
jobs = [1, 2, 3, 4], k = 4
4
k = n means every job gets its own worker. Max = max(jobs) = 4.
- Do not modify the inputs.
- Use only the standard library.
- An O(2^n) brute-force partition search will time out on 200k jobs.
- python environment
- python-pytest runner
- 8000ms judge budget
If jobs could be reordered freely, would the answer change? What problem does that turn into, and is it still tractable?
Keep moving through related algorithms & data structures problems and build a stronger search-friendly practice loop around this topic.
View track →