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.
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 →