hardBacktrackingPure DSA~40 min
Assign Jobs to Workers to Minimize the Busiest Worker
You distribute jobs of varying durations across k workers. Each job goes to exactly one worker, who runs jobs sequentially. Minimize the maximum total working time over all workers (the makespan).
Problem
Given an array jobs of job durations and an integer k workers, assign each job to a worker so that the maximum total working time among workers is minimized. Return that minimum possible maximum working time.
Input
An array jobs of durations and an integer k.
Output
An integer: the minimized maximum worker load.
Constraints
- 1 <= k <= jobs.length <= 12
- 1 <= jobs[i] <= 10^7
Examples
Example 1
Input
jobs = [3,2,3], k = 3
Output
3
Each worker takes one job; the max load is 3.
Example 2
Input
jobs = [1,2,4,7,8], k = 2
Output
11
Workers get {2,8} and {1,4,7}: max load 11.