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);
    }

    // Function to calculate the minimum sessions needed
    private int permute(int[] tasks, int currentSession, int sessionTime, 
      int mask) {
        String key = currentSession + " " + mask;

        // If all tasks are completed, return 1 session
        if (mask == (1 << tasks.length) - 1) {
            return 1;
        } else if (memo.containsKey(key)) { 
            // If memoization contains the calculated result, return the value
            return memo.get(key);
        } else {
            int res = Integer.MAX_VALUE;

            // Iterate through each task to find the minimum sessions required
            for (int i = 0; i < tasks.length; i++) {
                if (((mask >> i) & 1) == 1) {
                    continue; // Skip if task is completed
                }

                // If the current session time plus the task 
                // time exceeds the session time limit
                if (currentSession + tasks[i] > sessionTime) {
                    res = Math.min(
                            res,
                            1 + permute(
                              	  tasks,
                                  // Start a new session with the current task
                                  tasks[i], 
                                  sessionTime,
                                  mask | (1 << i)
                            )
                    );
                } else {
                    // Continue the current session with the current task
                    res = Math.min(
                            res,
                            permute(tasks,
                              currentSession + tasks[i],
                              sessionTime,
                              mask | (1 << i)
                            )
                    );
                }
            }

            // Store the calculated result in memoization
            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})$$