Minimum Number of Work Sessions to Finish the Tasks

You have n tasks. Task i takes tasks[i] hours. A work session is at most sessionTime hours of work in a row, followed by a break.

Minimum Number of Work Sessions to Finish the Tasks

Problem

You have n tasks. Task i takes tasks[i] hours. A work session is at most sessionTime hours of work in a row, followed by a break.

The rules are:

• If you start a task in a session, you must finish it in the same session.
• You can start a new task right after finishing the previous one.
• You can do the tasks in any order.

Return the minimum number of work sessions needed to finish all tasks.

sessionTime is always at least as big as the biggest task.

Examples

Example 1

Input: tasks = [1,2,3], sessionTime = 3
Output: 2

• Session 1: tasks 1 and 2 (1 + 2 = 3 hours).
• Session 2: task 3 (3 hours).

Example 2

Input: tasks = [3,1,3,1,1], sessionTime = 8
Output: 2

• Session 1: 3 + 1 + 3 + 1 = 8 hours.
• Session 2: the last task, 1 hour.

Example 3

Input: tasks = [1,2,3,4,5], sessionTime = 15
Output: 1

• All tasks together take 15 hours, so one session is enough.

Constraints

The constraints were not shared, so these are the usual ones for this problem:

• 1 <= n <= 14
• 1 <= tasks[i] <= 10
• max(tasks[i]) <= sessionTime <= 15

Note: n is small (at most 14). This is the hint that an exponential solution, such as backtracking or bitmask DP, is expected.

Main Idea

This is a bin packing problem. Each session is a bin with size sessionTime, and each task is an item. We want the fewest bins.

Bin packing is hard in general, so there is no fast greedy rule. But with n <= 14, we can try all the ways, using two methods:

• Backtracking: Put each task into a session, trying all choices, and prune bad paths.
• Bitmask DP: Remember the best answer for every subset of tasks.

Solution 1: Backtracking

We place tasks one by one. For each task, we try:

• Put it in one of the open sessions that still has room.
• Or open a new session for it.

We keep the best (smallest) number of sessions found so far.

var minSessions = function (tasks, sessionTime) {
    const n = tasks.length;

    // big tasks first: they fail early, so we prune more
    tasks.sort((a, b) => b - a);

    let best = n; // worst case: one session for each task
    const sessions = []; // sessions[k] = hours used in session k

    function dfs(i) {
        // already not better than the best answer
        if (sessions.length >= best) return;

        // all tasks are placed
        if (i === n) {
            best = sessions.length;
            return;
        }

        // try each open session
        for (let k = 0; k < sessions.length; k++) {
            if (sessions[k] + tasks[i] <= sessionTime) {
                sessions[k] += tasks[i];
                dfs(i + 1);
                sessions[k] -= tasks[i]; // undo
            }
        }

        // or open a new session
        sessions.push(tasks[i]);
        dfs(i + 1);
        sessions.pop(); // undo
    }

    dfs(0);
    return best;
};

How the Code Works

• sessions holds how many hours each open session has used.
• dfs(i) places task i.
• Prune: If we already have as many sessions as best, this path cannot win, so we stop.
• Base case: If i === n, all tasks are placed. We save sessions.length as the new best.
• Choices: Add the task to any session with enough room, or open a new one.
• After each recursive call, we undo the change, so the next choice starts clean.
• Sorting from big to small makes the large tasks fill sessions first, so bad paths end early.

Complexity

• Time Complexity: O(n!) in the worst case, but pruning makes it much faster in practice.
• Space Complexity: O(n)
  • The recursion depth and the sessions array are at most n.

Solution 2: Bitmask DP

Each subset of tasks can be written as a bitmask. Bit i is 1 if task i is in the subset.

Let dp[mask] be a pair [sessions, used]:

• sessions: the minimum number of sessions used for the tasks in mask.
• used: the hours used in the last session, with sessions as small as possible, and then used as small as possible.

We keep the last session as empty as possible, so more tasks can fit into it later.

Transition

For each mask, try to add one task i that is not in mask:

• If used + tasks[i] <= sessionTime, the task fits in the last session. The new state is [sessions, used + tasks[i]].
• Otherwise, we open a new session. The new state is [sessions + 1, tasks[i]].
• We keep the smaller pair, comparing sessions first and then used.

var minSessions = function (tasks, sessionTime) {
    const n = tasks.length;
    const full = (1 << n) - 1;

    // dp[mask] = [sessions, hours used in the last session]
    const dp = Array.from({ length: full + 1 }, () => [Infinity, Infinity]);

    // no tasks: we start with one empty session
    dp[0] = [1, 0];

    for (let mask = 0; mask < full; mask++) {
        const [sessions, used] = dp[mask];

        for (let i = 0; i < n; i++) {
            // task i is already in the mask
            if (mask & (1 << i)) continue;

            const next = mask | (1 << i);
            let candidate;

            if (used + tasks[i] <= sessionTime) {
                // fits in the current session
                candidate = [sessions, used + tasks[i]];
            } else {
                // open a new session
                candidate = [sessions + 1, tasks[i]];
            }

            const cur = dp[next];

            // keep the better pair: fewer sessions, then fewer hours used
            if (
                candidate[0] < cur[0] ||
                (candidate[0] === cur[0] && candidate[1] < cur[1])
            ) {
                dp[next] = candidate;
            }
        }
    }

    return dp[full][0];
};

How the Code Works

• Step 1: full = (1 << n) - 1 is the mask with all tasks. For n = 3, it is 111 in binary.
• Step 2: dp[0] = [1, 0] means: with no tasks, we have one empty session open.
• Step 3: We loop over masks in increasing order. A mask's next states have a bigger value, so dp[mask] is final when we read it.
• Step 4: For each task i not in the mask, we find the candidate state, and keep it if it is better.
• Step 5: dp[full][0] is the minimum number of sessions for all tasks.

Dry Run

Let us take tasks = [1, 2, 3] and sessionTime = 3.

The key point: from {1,2} with state [1, 3], adding 3 does not fit, so we open a new session. This gives [2, 3]. The final answer is 2.

Complexity

• Time Complexity: O(2^n * n)
  • There are 2^n masks, and each tries n tasks.
  • For n = 14, this is about 14 * 16384 = 229376 steps.
• Space Complexity: O(2^n)
  • The dp array has 2^n entries.

Comparison

Summary

• This is a bin packing problem with a small n, so we can try all the ways.
• Backtracking puts each task in an open session or opens a new one. Sorting big tasks first and pruning at best makes it fast.
• Bitmask DP stores, for each subset of tasks, the fewest sessions and the hours used in the last session. We keep the best pair.
• Always compare sessions first, then used, because a less-filled last session leaves more room.
• Bitmask DP runs in O(2^n * n) time and uses O(2^n) space.