{x}
blog image

Find Minimum Time to Finish All Jobs II

Solution Explanation: Greedy Approach

This problem can be efficiently solved using a greedy approach. The core idea is to pair the most demanding jobs (longest job durations) with the most capable workers (workers with the highest working capacity per day). This pairing strategy minimizes the overall time required to complete all jobs.

Algorithm:

  1. Sort: Sort both the jobs and workers arrays in ascending order. This ensures that we can directly pair the largest jobs with the most efficient workers for optimal time allocation.

  2. Pair and Calculate: Iterate through the sorted arrays, pairing the i-th job with the i-th worker. For each pair, calculate the number of days required to complete the job using this worker: ceil(jobs[i] / workers[i]). The ceil function is crucial because we need to round up to the nearest whole number of days, as we can't complete fractions of a job in a day.

  3. Find Maximum: Track the maximum number of days needed across all job-worker pairs. This maximum value represents the minimum number of days required to complete all jobs when employing the optimal pairing strategy.

  4. Return: Return the maximum number of days found in the previous step.

Time Complexity: O(n log n) - dominated by the sorting step of the arrays, where n is the number of jobs (and workers).

Space Complexity: O(log n) - space used by sorting algorithms (typically in-place sorting or using a small auxiliary stack). This is negligible compared to the input size.

Code Examples (Python, Java, C++, Go, TypeScript, Rust, Javascript):

The code examples below implement the greedy approach described above. The comments in the Python code highlight the key steps.

Python:

class Solution:
    def minimumTime(self, jobs: List[int], workers: List[int]) -> int:
        jobs.sort()  # Sort jobs in ascending order
        workers.sort() # Sort workers in ascending order
        max_days = 0
        for i in range(len(jobs)):
            days_needed = (jobs[i] + workers[i] - 1) // workers[i] #Calculate days needed and round up
            max_days = max(max_days, days_needed) # Update max_days if necessary
        return max_days

Java:

import java.util.Arrays;
 
class Solution {
    public int minimumTime(int[] jobs, int[] workers) {
        Arrays.sort(jobs);
        Arrays.sort(workers);
        int maxDays = 0;
        for (int i = 0; i < jobs.length; ++i) {
            maxDays = Math.max(maxDays, (jobs[i] + workers[i] - 1) / workers[i]);
        }
        return maxDays;
    }
}

C++:

#include <algorithm>
#include <vector>
 
class Solution {
public:
    int minimumTime(std::vector<int>& jobs, std::vector<int>& workers) {
        std::sort(jobs.begin(), jobs.end());
        std::sort(workers.begin(), workers.end());
        int maxDays = 0;
        for (size_t i = 0; i < jobs.size(); ++i) {
            maxDays = std::max(maxDays, (jobs[i] + workers[i] - 1) / workers[i]);
        }
        return maxDays;
    }
};

Go:

import "sort"
import "math"
 
func minimumTime(jobs []int, workers []int) int {
	sort.Ints(jobs)
	sort.Ints(workers)
	maxDays := 0
	for i := range jobs {
		maxDays = int(math.Max(float64(maxDays), math.Ceil(float64(jobs[i])/float64(workers[i]))))
	}
	return maxDays
}

TypeScript:

function minimumTime(jobs: number[], workers: number[]): number {
    jobs.sort((a, b) => a - b);
    workers.sort((a, b) => a - b);
    let maxDays = 0;
    for (let i = 0; i < jobs.length; i++) {
        maxDays = Math.max(maxDays, Math.ceil(jobs[i] / workers[i]));
    }
    return maxDays;
}

Rust:

impl Solution {
    pub fn minimum_time(mut jobs: Vec<i32>, mut workers: Vec<i32>) -> i32 {
        jobs.sort();
        workers.sort();
        let mut max_days = 0;
        for i in 0..jobs.len() {
            max_days = max(max_days, (jobs[i] + workers[i] -1) / workers[i]);
        }
        max_days
    }
}

JavaScript:

/**
 * @param {number[]} jobs
 * @param {number[]} workers
 * @return {number}
 */
var minimumTime = function(jobs, workers) {
    jobs.sort((a, b) => a - b);
    workers.sort((a, b) => a - b);
    let maxDays = 0;
    for (let i = 0; i < jobs.length; i++) {
        maxDays = Math.max(maxDays, Math.ceil(jobs[i] / workers[i]));
    }
    return maxDays;
};

These code examples all achieve the same result using the greedy strategy. They demonstrate the efficient and concise nature of this approach to the problem.