1723. Find Minimum Time to Finish All Jobs

This page provides solutions for the leetcode problem 1723. Find Minimum Time to Finish All Jobs.

Problem Explanation

The problem is asking us to divide the jobs among $\text{K}$ workers in such a way the maximum working time of any worker is minimized.

Solution

For this problem, we need to consider all possible distribution possibilities. Therefore, we use the backtracking technique. More such problem can be found here.

Java

class Solution {
  private int min = Integer.MAX_VALUE;

  public int minimumTimeRequired(int[] jobs, int k) {
    backtrack(jobs, 0, new int[k]);
    return min;
  }

  private void backtrack(int[] jobs, int index, int[] workers) {
    if(index == jobs.length) {
      min = Math.min(min, max(workers));
    } 
    else {
      for(int i = 0; i < workers.length; i++) {
        if(i > 0 && workers[i] == workers[i - 1]) continue;
        if(workers[i] + jobs[index] > min) continue;
        workers[i] += jobs[index];
        backtrack(jobs, index + 1, workers);
        workers[i] -= jobs[index];
      }
    }
  }

  private int max(int[] array) {
    int maxValue = Integer.MIN_VALUE;
    for(int i = 0; i < array.length; i++) maxValue = Math.max(maxValue, array[i]);
    return maxValue;
  }
}

Complexity

Let $\text{N}$ be the length of the input array $\text{jobs}$ and $\text{K}$ be the number of workers.

Time Complexity

Each of the $\text{N}$ job has $K$ workers to choose from, so time complexity will be:

$$\text{O}(\text{K} ^ \text{N})$$

Space Complexity

Since there are $\text{N}$ jobs to assign to each worker, the stack size for the backtracking will go upto $\text{N}$, so space complexity will be:

$$\text{O}(\text{N})$$