Find Minimum Time to Finish All Jobs - Practice Coding Problems

Find Minimum Time to Finish All Jobs - Problem

You are given an integer array jobs, where jobs[i] is the amount of time it takes to complete the i-th job.

There are k workers that you can assign jobs to. Each job should be assigned to exactly one worker. The working time of a worker is the sum of the time it takes to complete all jobs assigned to them. Your goal is to devise an optimal assignment such that the maximum working time of any worker is minimized.

Return the minimum possible maximum working time of any assignment.

Input & Output

Example 1 — Basic Case

$ Input: jobs = [3,2,3], k = 3

› Output: 3

💡 Note: Assign each job to a different worker: Worker 1 gets job with time 3, Worker 2 gets job with time 2, Worker 3 gets job with time 3. Maximum working time is max(3,2,3) = 3.

Example 2 — Optimal Assignment

$ Input: jobs = [1,2,4,7,8], k = 2

› Output: 11

💡 Note: Assign jobs optimally: Worker 1 gets jobs [1,2,8] with total time 11, Worker 2 gets jobs [4,7] with total time 11. Both workers finish at time 11.

Example 3 — Single Worker

$ Input: jobs = [5,3,7], k = 1

› Output: 15

💡 Note: Only one worker must do all jobs: 5 + 3 + 7 = 15. The minimum possible maximum working time is 15.

Constraints

1 ≤ k ≤ jobs.length ≤ 12
1 ≤ jobs[i] ≤ 10⁷

Visualization

Tap to expand

Understanding the Visualization

Input

Jobs [3,2,3] and k=3 workers

Process

Find assignment minimizing maximum worker time

Output

Optimal assignment with max time = 3

Key Takeaway

🎯 Key Insight: Binary search the maximum time and verify feasibility with backtracking

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is to use binary search on the answer space (maximum working time) combined with backtracking to verify feasibility. The optimal approach binary searches the range [max(jobs), sum(jobs)] and uses backtracking to check if jobs can be assigned within each candidate time limit. Time: O(log(sum) × k^n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Assignments	O(k^n)	O(n)	Generate all possible job assignments and find minimum maximum workload
Binary Search on Answer	O(log(sum) × k^n)	O(n)	Binary search the minimum possible maximum time, verify feasibility with backtracking
Backtracking with Pruning	O(k^n)	O(n)	Systematic search with early termination when current assignment exceeds best found

Brute Force - Try All Assignments — Algorithm Steps

Generate all possible assignments of jobs to workers
Calculate maximum workload for each assignment
Return the minimum of all maximum workloads

Visualization

Tap to expand

Step-by-Step Walkthrough

Input

jobs=[3,2,3], k=3 workers

Try All

Generate all 3^3=27 possible assignments

Result

Find assignment with minimum maximum workload

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int minMaxTime = INT_MAX;

int max(int* arr, int size) {
    int maxVal = arr[0];
    for (int i = 1; i < size; i++) {
        if (arr[i] > maxVal) maxVal = arr[i];
    }
    return maxVal;
}

void backtrack(int* jobs, int jobsSize, int* workers, int k, int jobIdx) {
    if (jobIdx == jobsSize) {
        int maxTime = max(workers, k);
        if (maxTime < minMaxTime) {
            minMaxTime = maxTime;
        }
        return;
    }
    
    for (int i = 0; i < k; i++) {
        workers[i] += jobs[jobIdx];
        backtrack(jobs, jobsSize, workers, k, jobIdx + 1);
        workers[i] -= jobs[jobIdx];
    }
}

int solution(int* jobs, int jobsSize, int k) {
    int* workers = (int*)calloc(k, sizeof(int));
    minMaxTime = INT_MAX;
    backtrack(jobs, jobsSize, workers, k, 0);
    free(workers);
    return minMaxTime;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int jobs[20], jobsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            jobs[jobsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(jobs, jobsSize, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k^n)

For each of n jobs, we try k workers, resulting in k^n combinations

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth of n for exploring assignments

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Assignments — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler