Find Minimum Time to Finish All Jobs II - Practice Coding Problems

Find Minimum Time to Finish All Jobs II - Problem

You are given two 0-indexed integer arrays jobs and workers of equal length, where jobs[i] is the amount of time needed to complete the i-th job, and workers[j] is the amount of time the j-th worker can work each day.

Each job should be assigned to exactly one worker, such that each worker completes exactly one job.

Return the minimum number of days needed to complete all the jobs after assignment.

Input & Output

Example 1 — Basic Case

$ Input: jobs = [3,2,3], workers = [1,1,1]

› Output: 3

💡 Note: Each worker can work 1 hour per day. Jobs take 3, 2, and 3 hours respectively. The workers need ceil(3/1)=3, ceil(2/1)=2, and ceil(3/1)=3 days. Maximum is 3 days.

Example 2 — Optimal Assignment

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

› Output: 2

💡 Note: Optimal assignment: job 8→worker 7 (2 days), job 7→worker 4 (2 days), job 4→worker 4 (1 day), job 2→worker 2 (1 day), job 1→worker 1 (1 day). Maximum is 2 days.

Example 3 — Equal Capacity

$ Input: jobs = [5,5,5], workers = [5,5,5]

› Output: 1

💡 Note: Each worker can complete their assigned job in exactly 1 day since job time equals worker capacity.

Constraints

1 ≤ jobs.length == workers.length ≤ 12
1 ≤ jobs[i], workers[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Two arrays: jobs=[3,2,3], workers=[1,1,1]

Assignment

Each job assigned to exactly one worker

Days Calculation

Worker days = ceil(job_time/worker_capacity)

Output

Maximum days across all workers

Key Takeaway

🎯 Key Insight: The bottleneck determines completion time - minimize the maximum days any worker needs

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Facebook 12

The key insight is that we want to minimize the maximum days needed across all workers. The optimal solution uses binary search on the answer to find the minimum feasible days, checking each candidate by greedily assigning jobs to workers. Time: O(n² log(max(jobs))), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Sort and Match Optimally	O(n log n)	O(1)	Sort jobs descending and workers ascending, then pair them optimally
Brute Force - Try All Permutations	O(n! × n)	O(n)	Generate all possible job-to-worker assignments and find minimum days
Optimal - Binary Search on Answer	O(n² log(max(jobs)))	O(1)	Binary search on the number of days, check if assignment is possible

Greedy - Sort and Match Optimally — Algorithm Steps

Sort jobs in descending order
Sort workers in ascending order
Pair each job with corresponding worker and calculate ceil(job/worker)

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Arrays

Jobs descending, workers ascending

Pair Optimally

Match hardest jobs with strongest workers

Calculate Days

Find maximum days across all pairs

Code -

solution.c — C

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

int compareDesc(const void* a, const void* b) {
    return (*(int*)b - *(int*)a);
}

int compareAsc(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* jobs, int* workers, int n) {
    // Sort jobs descending, workers ascending
    qsort(jobs, n, sizeof(int), compareDesc);
    qsort(workers, n, sizeof(int), compareAsc);
    
    int maxDays = 0;
    
    // Pair each job with corresponding worker
    for (int i = 0; i < n; i++) {
        int daysNeeded = (int)ceil((double)jobs[i] / workers[i]);
        if (daysNeeded > maxDays) maxDays = daysNeeded;
    }
    
    return maxDays;
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    // Simple parsing for arrays
    int jobs[100], workers[100];
    int n = 0;
    
    // Parse jobs array
    char* token = strtok(line1 + 1, ",]");
    while (token != NULL) {
        jobs[n] = atoi(token);
        token = strtok(NULL, ",]");
        n++;
    }
    
    // Parse workers array
    int idx = 0;
    token = strtok(line2 + 1, ",]");
    while (token != NULL && idx < n) {
        workers[idx] = atoi(token);
        token = strtok(NULL, ",]");
        idx++;
    }
    
    printf("%d\n", solution(jobs, workers, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting both arrays takes O(n log n), pairing takes O(n)

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

485 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

Greedy - Sort and Match Optimally — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler