1986. Minimum Number of Work...

This page provides solutions for the leetcode problem 1986. Minimum Number of Work Sessions to Finish the Tasks.

Problem Explanation

Problem requires us to calculate the number of work sessions required to finish all the task given by task array. You should finish the given tasks in a way that satisfies the following conditions:

• If you start a task in a work session, you must complete it in the same work session.
• You can start a new task immediately after finishing the previous one.
• You may complete the tasks in any order.

Solution

This problem can be solved using the Permutations technique. More such questions can be found here.

Java

import java.util.HashMap;

class Solution {
  private HashMap<String, Integer> memo;

  public int minSessions(int[] tasks, int sessionTime) {
    memo = new HashMap<>();
    return permute(tasks, 0, sessionTime, 0);
  }

  private int permute(int[] tasks, int currentSession, int sessionTime, int mask) {
    String key = currentSession + " " + mask;
    if(mask == (1 << tasks.length) - 1) return 1;
    else if(memo.containsKey(key)) return memo.get(key);
    else {
      int res = Integer.MAX_VALUE;
      for(int i = 0; i < tasks.length; i++) {
        if(((mask >> i) & 1) == 1) continue;
        if(currentSession + tasks[i] > sessionTime) {
          res = Math.min(
            res,
            1 + permute(tasks, tasks[i], sessionTime, mask | (1 << i))
          );
        } 
        else {
          res = Math.min(
            res,
            permute(tasks, currentSession + tasks[i], sessionTime, mask | (1 << i))
          );
        }
      }
      memo.put(key, res);
      return res;
    }
  }
}

Complexity

Let's say there are $\text{N}$ elements in an array, and we need to create $\text{K}$ subsets.

Time Complexity

The time complexity is $\text{O}(2^{\text{N}})$ for creating a single subset, as we can either choose or skip each element of an array, and $\text{O}(\text{K})$ for creating $\text{K}$ subsets, so total time complexity will be:

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

Space Complexity

At any given time, the excution stack will have at most $\text{N}$ elements, so space complexity will be:

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