# Minimum Number of Work Sessions to Finish the Tasks
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-work-sessions-to-finish-the-tasks)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-work-sessions-to-finish-the-tasks
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
**Companies:** [Swiggy](https://scaleengineer.com/companies/swiggy)
---
## Problem
There are `n` tasks assigned to you. The task times are represented as an integer array `tasks` of length `n`, where the `ith` task takes `tasks[i]` hours to finish. A **work session** is when you work for **at most** `sessionTime` consecutive hours and then take a break.

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**.

Given `tasks` and `sessionTime`, return _the **minimum** number of **work sessions** needed to finish all the tasks following the conditions above._

The tests are generated such that `sessionTime` is **greater** than or **equal** to the **maximum** element in `tasks[i]`.

**Example 1:**

**Input:** tasks = [1,2,3], sessionTime = 3
**Output:** 2
**Explanation:** You can finish the tasks in two work sessions.
- First work session: finish the first and the second tasks in 1 + 2 = 3 hours.
- Second work session: finish the third task in 3 hours.

**Example 2:**

**Input:** tasks = [3,1,3,1,1], sessionTime = 8
**Output:** 2
**Explanation:** You can finish the tasks in two work sessions.
- First work session: finish all the tasks except the last one in 3 + 1 + 3 + 1 = 8 hours.
- Second work session: finish the last task in 1 hour.

**Example 3:**

**Input:** tasks = [1,2,3,4,5], sessionTime = 15
**Output:** 1
**Explanation:** You can finish all the tasks in one work session.

**Constraints:**

* `n == tasks.length`
* `1 <= n <= 14`
* `1 <= tasks[i] <= 10`
* `max(tasks[i]) <= sessionTime <= 15`

# Approaches
## Recursive Backtracking with Pruning
This approach uses a brute-force recursive strategy to explore all possible ways of assigning tasks to work sessions. It tries to place each task one by one, either into an existing session or by starting a new one. The search space is pruned by keeping track of the minimum number of sessions found so far and abandoning paths that cannot yield a better result.
**Time:** O(n * B_n), where B_n is the n-th Bell number. This is because we are exploring all partitions of the set of tasks. This is prohibitively slow for n=14. · **Space:** O(n), for the recursion depth and the `sessions` array.
**Pros:** Conceptually straightforward and relatively easy to implement.; Uses minimal extra space, primarily for the recursion stack.
**Cons:** Extremely slow for the given constraints (`n <= 14`) due to its exponential time complexity, which is related to Bell numbers.; Likely to result in a 'Time Limit Exceeded' error on most competitive programming platforms.; Performance is highly dependent on the specific input values and the effectiveness of pruning.
### Explanation
The backtracking algorithm systematically generates all valid partitions of tasks into sessions. We define a recursive function that takes the index of the current task to be placed and the state of the current sessions (how much time is used in each).

For each task, we try to fit it into any of the already started sessions. If it fits, we add it and recurse for the next task. After returning, we backtrack by removing the task to explore other possibilities. If the task cannot fit in any existing session, or as another alternative, we can place it in a new session and recurse. This process continues until all tasks are placed. The minimum number of sessions used across all valid full assignments is the answer.

To make this more practical, we use pruning. We maintain a variable holding the minimum sessions found so far. If the number of sessions we are currently using already meets or exceeds this minimum, we know this path won't lead to a better solution, so we stop exploring it.

```java
class Solution {
    private int minSessionsCount;
    private int[] tasks;
    private int n;
    private int sessionTime;

    public int minSessions(int[] tasks, int sessionTime) {
        this.tasks = tasks;
        this.n = tasks.length;
        this.sessionTime = sessionTime;
        this.minSessionsCount = n; // Worst case is one session per task

        int[] sessions = new int[n];
        findMinSessions(0, 0, sessions);
        return minSessionsCount;
    }

    private void findMinSessions(int taskIndex, int currentSessionCount, int[] sessions) {
        // Pruning: If we already have more or equal sessions than the best found so far.
        if (currentSessionCount >= minSessionsCount) {
            return;
        }

        // Base case: All tasks have been assigned.
        if (taskIndex == n) {
            minSessionsCount = Math.min(minSessionsCount, currentSessionCount);
            return;
        }

        // Option 1: Assign the current task to an existing session.
        for (int i = 0; i < currentSessionCount; i++) {
            if (sessions[i] + tasks[taskIndex] <= sessionTime) {
                sessions[i] += tasks[taskIndex];
                findMinSessions(taskIndex + 1, currentSessionCount, sessions);
                sessions[i] -= tasks[taskIndex]; // Backtrack
            }
        }

        // Option 2: Start a new session for the current task.
        sessions[currentSessionCount] = tasks[taskIndex];
        findMinSessions(taskIndex + 1, currentSessionCount + 1, sessions);
        sessions[currentSessionCount] = 0; // Backtrack
    }
}
```
### Algorithm
- The core of the approach is a recursive function, let's call it `dfs(taskIndex, sessionCount, sessions)`, where `taskIndex` is the index of the current task to assign, `sessionCount` is the number of sessions currently in use, and `sessions` is an array storing the time consumed in each session.
- A global variable, `minSessions`, is used to keep track of the minimum number of sessions found so far, initialized to a large value (e.g., `n`).
- **Base Case:** When `taskIndex` reaches `n`, it means all tasks have been assigned. We then update `minSessions` with the current `sessionCount` if it's smaller.
- **Pruning:** Before proceeding, the function checks if `sessionCount` is already greater than or equal to `minSessions`. If so, this path cannot lead to a better solution, and the function returns immediately.
- **Recursive Step:** For the current task `tasks[taskIndex]`, we explore two possibilities:
  1. **Assign to an existing session:** Iterate through the `sessionCount` active sessions. If the current task fits into session `i` (i.e., `sessions[i] + tasks[taskIndex] <= sessionTime`), place it there, and make a recursive call `dfs(taskIndex + 1, sessionCount, sessions)`. After the call returns, backtrack by removing the task from the session.
  2. **Start a new session:** Place the current task into a new session `sessionCount`. Make a recursive call `dfs(taskIndex + 1, sessionCount + 1, sessions)`. Backtrack after the call.
- To potentially improve performance through better pruning, the `tasks` array can be sorted in descending order before starting the recursion. This heuristic places larger, more restrictive tasks first.

## Dynamic Programming with Bitmasking
This approach uses dynamic programming with bitmasking to find the optimal solution efficiently. The state of the DP is defined by a bitmask representing the subset of tasks that have been completed. For each subset, we compute the minimum number of sessions required and the time consumed in the last session.
**Time:** O(n * 2^n). We iterate through `2^n` masks, and for each mask, we iterate through `n` tasks. · **Space:** O(2^n) to store the DP table for all `2^n` masks.
**Pros:** Guaranteed to find the minimum number of sessions.; Efficient enough to pass within the time limits for the given constraints.; Systematically builds the solution from smaller subproblems to larger ones.
**Cons:** Requires O(2^n) space, which can be substantial (e.g., for n=14, it's 16384 entries).; The logic for bitmask DP can be more complex to understand and implement correctly compared to a simple recursive solution.
### Explanation
Given the constraint `n <= 14`, an exponential time complexity in `n` is acceptable. This suggests a solution involving bitmask DP. We can define a DP state `dp[mask]` that stores the optimal arrangement for the subset of tasks represented by the bitmask `mask`.

Specifically, `dp[mask]` will be a pair `(numberOfSessions, timeUsedInLastSession)`. Our goal is to minimize `numberOfSessions`, and for an equal number of sessions, we want to minimize `timeUsedInLastSession` to maximize the chance of fitting more tasks into it.

We iterate through all possible masks from 1 up to `2^n - 1`. For each `mask`, we compute its `dp` value by transitioning from smaller submasks. To compute `dp[mask]`, we can try adding each task `i` (where the `i`-th bit is set in `mask`) to the optimal arrangement for the submask `mask` without task `i` (i.e., `mask ^ (1 << i)`). Based on the time left in the last session of the subproblem, we either add the current task to it or start a new session. We keep the best result among all choices for task `i`.

```java
class Solution {
    public int minSessions(int[] tasks, int sessionTime) {
        int n = tasks.length;
        int numMasks = 1 << n;
        // dp[mask][0] = min sessions, dp[mask][1] = min time in last session
        int[][] dp = new int[numMasks][2];

        for (int i = 1; i < numMasks; i++) {
            dp[i][0] = n + 1; // Initialize with a value larger than any possible answer
            dp[i][1] = sessionTime + 1;
        }

        // Base case: 0 tasks, 0 sessions. Time is set to be greater than sessionTime
        // so that the first task always starts a new session.
        dp[0][0] = 0;
        dp[0][1] = sessionTime + 1;

        for (int mask = 1; mask < numMasks; mask++) {
            for (int i = 0; i < n; i++) {
                // Check if task i is in the current subset (mask)
                if (((mask >> i) & 1) == 1) {
                    int prevMask = mask ^ (1 << i);
                    int prevSessions = dp[prevMask][0];
                    int prevTime = dp[prevMask][1];

                    int newSessions, newTime;
                    if (prevTime + tasks[i] <= sessionTime) {
                        // Add task i to the last session of the previous state
                        newSessions = prevSessions;
                        newTime = prevTime + tasks[i];
                    } else {
                        // Start a new session for task i
                        newSessions = prevSessions + 1;
                        newTime = tasks[i];
                    }

                    // If we found a better arrangement (fewer sessions, or same sessions with less time in the last one)
                    if (newSessions < dp[mask][0] || (newSessions == dp[mask][0] && newTime < dp[mask][1])) {
                        dp[mask][0] = newSessions;
                        dp[mask][1] = newTime;
                    }
                }
            }
        }

        return dp[numMasks - 1][0];
    }
}
```
### Algorithm
- The state for our dynamic programming will be `dp[mask]`, which stores a pair of values: `{numberOfSessions, timeOfLastSession}` for the subset of tasks represented by `mask`.
- A bitmask `mask` is an integer where the `i`-th bit is 1 if the `i`-th task is included in the subset, and 0 otherwise.
- The goal is to minimize `numberOfSessions`, and as a tie-breaker, minimize `timeOfLastSession` to leave more capacity for subsequent tasks.
- The `dp` table of size `2^n` is initialized. `dp[0]` is the base case, representing zero tasks. We can set it to `{0, sessionTime + 1}`. This indicates 0 sessions are used, and the 'last session' is considered full, which conveniently forces the first task to start a new session.
- We iterate through all masks from 1 to `(1 << n) - 1`.
- For each `mask`, we determine its `dp` value by considering adding each task `i` present in the `mask` to the configuration of `prev_mask = mask ^ (1 << i)`.
- Let `(prevSessions, prevTime) = dp[prev_mask]`. When adding `tasks[i]`:
  - If `prevTime + tasks[i] <= sessionTime`, the task fits in the last session. The new state is `{prevSessions, prevTime + tasks[i]}`.
  - Otherwise, a new session must be started. The new state is `{prevSessions + 1, tasks[i]}`.
- We update `dp[mask]` with the best state (minimum sessions, then minimum time) found by trying all tasks `i` in the `mask`.
- The final answer is the number of sessions stored in `dp[(1 << n) - 1]`.

# Solutions
### Java

```java
class Solution {
public
  int minSessions(int[] tasks, int sessionTime) {
    int n = tasks.length;
    boolean[] ok = new boolean[1 << n];
    for (int i = 1; i < 1 << n; ++i) {
      int t = 0;
      for (int j = 0; j < n; ++j) {
        if ((i >> j & 1) == 1) {
          t += tasks[j];
        }
      }
      ok[i] = t <= sessionTime;
    }
    int[] f = new int[1 << n];
    Arrays.fill(f, 1 << 30);
    f[0] = 0;
    for (int i = 1; i < 1 << n; ++i) {
      for (int j = i; j > 0; j = (j - 1) & i) {
        if (ok[j]) {
          f[i] = Math.min(f[i], f[i ^ j] + 1);
        }
      }
    }
    return f[(1 << n) - 1];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minSessions(vector<int> &tasks, int sessionTime) {
    int n = tasks.size();
    bool ok[1 << n];
    memset(ok, false, sizeof(ok));
    for (int i = 1; i < 1 << n; ++i) {
      int t = 0;
      for (int j = 0; j < n; ++j) {
        if (i >> j & 1) {
          t += tasks[j];
        }
      }
      ok[i] = t <= sessionTime;
    }
    int f[1 << n];
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i < 1 << n; ++i) {
      for (int j = i; j; j = (j - 1) & i) {
        if (ok[j]) {
          f[i] = min(f[i], f[i ^ j] + 1);
        }
      }
    }
    return f[(1 << n) - 1];
  }
};

```

### Python

```python
class Solution:
    def minSessions(self, tasks: List[int], sessionTime: int) -> int: n = len(tasks) ok = [False] * (1 << n) for i in range(1, 1 << n): t = sum(tasks[j] for j in range(n) if i >> j & 1) ok[i] = t <= sessionTime f = [inf] * (1 << n) f[0] = 0 for i in range(1, 1 << n): j = i while j: if ok[j]: f[i] = min(f[i], f[i ^ j] + 1) j = (j - 1) & i return f[- 1]

```