Minimum Number of Work Sessions to Finish the Tasks

June 6, 20267 min read

leetcodeproblemmediumdynamic-programmingbit-manipulation

You are given an array tasks where tasks[i] is the number of hours task i takes, and an integer sessionTime. In each work session you can work for at most sessionTime consecutive hours. You can complete any subset of tasks during a session as long as the total time does not exceed sessionTime, but you cannot split a single task across two sessions. Return the minimum number of work sessions needed to finish all the tasks.

This is LeetCode 1986: Minimum Number of Work Sessions to Finish the Tasks, and it is a beautiful example of bitmask DP. The trick is to represent which tasks have been completed as a bitmask, and for each state, track both the number of sessions used and how much time is left in the current session.

Optimal packing of tasks [1, 2, 3] into sessions of length 4. Task 3 and task 1 share a session (3 + 1 = 4). Task 2 goes alone.

Why bitmask DP?

At first glance this looks like a bin packing problem. And it is, sort of. But the constraint is small: tasks has at most 14 elements. That is a strong hint. With n up to 14, the total number of subsets is 2^14 = 16384. That is small enough to enumerate every possible combination of completed tasks.

The key insight: if you know exactly which tasks are done, and you know how much time is left in the current session, you have all the information you need to decide what to do next. You do not need to know the order tasks were completed or which sessions they landed in. The bitmask captures the full state.

This is the same "represent subsets as bits" idea you see in problems like Subsets, but here you use it for DP rather than enumeration.

The state

Define dp[mask] as a tuple (sessions, remaining) where:

mask is a bitmask of length n. Bit i is 1 if task i has been completed.
sessions is the minimum number of work sessions used so far.
remaining is the time left in the current (most recent) session, maximized to allow the best future packing.

The base case is dp[0] = (0, 0). No tasks done, zero sessions used, zero time remaining (we have not started any session yet).

The transition

For each state mask, try adding each task i that has not been completed yet (bit i is 0 in mask). Let new_mask = mask | (1 << i).

Two cases:

Task fits in the current session: tasks[i] is at most remaining. Use the current session. The new state is (sessions, remaining - tasks[i]).
Task does not fit: start a new session. The new state is (sessions + 1, sessionTime - tasks[i]).

For each new_mask, keep the best (sessions, remaining). "Best" means fewer sessions first, then more remaining time (to leave room for future tasks).

The code

def min_sessions(tasks, session_time):
    n = len(tasks)
    full = (1 << n) - 1
    dp = [(n, 0)] * (full + 1)
    dp[0] = (0, 0)

    for mask in range(full + 1):
        sessions, remaining = dp[mask]
        for i in range(n):
            if mask & (1 << i):
                continue
            new_mask = mask | (1 << i)
            if tasks[i] <= remaining:
                candidate = (sessions, remaining - tasks[i])
            else:
                candidate = (sessions + 1, session_time - tasks[i])
            if candidate < dp[new_mask]:
                dp[new_mask] = candidate

    return dp[full][0]

Notice the comparison candidate < dp[new_mask]. Python compares tuples lexicographically: it first compares sessions, and only if those are equal does it compare remaining. Since we want fewer sessions and, as a tiebreaker, more remaining time, a smaller (sessions, remaining) with fewer sessions always wins. But wait, for the same number of sessions, we want more remaining time, not less. The trick is that remaining is what is left, so a smaller remaining means less room. We actually want the larger remaining when sessions are tied.

Let me fix that. We need to compare correctly: fewer sessions is better, and for the same number of sessions, more remaining time is better. One clean way is to negate remaining:

def min_sessions(tasks, session_time):
    n = len(tasks)
    full = (1 << n) - 1
    INF = (n + 1, 0)
    dp = [INF] * (full + 1)
    dp[0] = (0, 0)

    for mask in range(full + 1):
        sessions, remaining = dp[mask]
        if dp[mask] == INF:
            continue
        for i in range(n):
            if mask & (1 << i):
                continue
            new_mask = mask | (1 << i)
            if tasks[i] <= remaining:
                candidate = (sessions, remaining - tasks[i])
            else:
                candidate = (sessions + 1, session_time - tasks[i])
            if candidate[0] < dp[new_mask][0] or (
                candidate[0] == dp[new_mask][0] and candidate[1] > dp[new_mask][1]
            ):
                dp[new_mask] = candidate

    return dp[full][0]

The comparison now explicitly says: pick the candidate with fewer sessions, or if sessions are tied, the one with more remaining time.

Practice bitmask DP with spaced repetition

Step-by-step walkthrough

Let's trace through tasks = [1, 2, 3] and sessionTime = 4. There are 3 tasks, so masks range from 000 (nothing done) to 111 (all done). For each mask, we track (sessions, remaining).

Base case: mask = 000 (no tasks completed)

No tasks done yet. We have 0 sessions used and 4 hours remaining (we start a fresh session when needed).

Try adding task 0 (1h): mask 000 -> 001

Task 0 costs 1 hour. It fits in a new session of 4 hours, leaving 3 hours. Sessions = 1.

Try adding task 1 (2h): mask 000 -> 010

Task 1 costs 2 hours. New session with 2 hours remaining. Sessions = 1.

Try adding task 2 (3h): mask 000 -> 100

Task 2 costs 3 hours. New session with 1 hour remaining. Sessions = 1.

From mask 001 (task 0 done, 3h left), add task 1 (2h): -> 011

Task 1 fits in the current session (2 out of 3 remaining). Still 1 session, 1 hour left.

From mask 100 (task 2 done, 1h left), add task 0 (1h): -> 101

Task 0 fits exactly (1h fits in 1h remaining). Session is full. Still only 1 session used.

From mask 101, add task 1 (2h): needs new session -> 111

Task 1 does not fit (2 > 0 remaining). Start a new session. Total = 2 sessions, 2 hours left. This is the optimal: dp[111] = (2, 2).

Final answer: all tasks completed in 2 sessions

The best path: assign tasks 2 and 0 to session 1 (3h + 1h = 4h), then task 1 to session 2 (2h). Minimum sessions = 2.

The optimal assignment puts tasks 2 (3h) and 0 (1h) together in one session (using all 4 hours), then task 1 (2h) in a second session. Two sessions total.

Why the comparison matters

The remaining time tiebreaker is critical. Consider tasks = [2, 3, 3] with sessionTime = 5. If you assign task 0 (2h) first, you have 3h left. That is enough for task 1 (3h), so both fit in one session. But if you had used a different ordering that left only 2h remaining, task 1 would not fit and you would need an extra session.

By always preferring the state with more remaining time (when sessions are tied), you give future tasks the best chance of fitting into the current session.

Complexity analysis

Metric	Value	Notes
Time	O(n * 2^n)	For each of the 2^n masks, try n tasks
Space	O(2^n)	One DP entry per mask

With n at most 14, this gives roughly 14 * 16384 = 229,376 operations. That is very fast.

Bitmask DP problems almost always have small n (usually 20 or less). If you see n up to about 14-20 in the constraints, bitmask DP should be one of the first techniques you consider.

The building blocks

This problem combines two fundamental patterns:

1. Bitmask subset representation

Using an integer's bits to represent which elements from a set have been selected. Bit i being 1 means element i is included. This is the same idea behind Subsets, but used here as a DP state rather than for enumeration.

The key operations:

mask & (1 << i): check if task i is in the set
mask | (1 << i): add task i to the set
(1 << n) - 1: the mask where all n tasks are included

2. DP with compound state

Instead of tracking a single value per state (like a count or a cost), each DP entry holds a tuple (sessions, remaining). The ordering on this tuple determines which states dominate. This pattern appears whenever a greedy packing decision depends on more than one variable.

These two building blocks combine: the bitmask gives you a way to enumerate all possible progress states, and the compound state lets you make optimal packing decisions at each step.

Edge cases to watch for

Single task: tasks = [5], sessionTime = 5. One session, trivially.
Every task fills a session: tasks = [3, 3, 3], sessionTime = 3. Answer is 3. No two tasks can share a session.
All tasks fit in one session: tasks = [1, 1, 1], sessionTime = 5. Answer is 1. The sum (3) is at most sessionTime.
n = 1: always 1 session. The constraints guarantee each task fits in a session (tasks[i] is at most sessionTime).
Large tasks with small gaps: tasks = [4, 4, 1], sessionTime = 5. Tasks 0 and 2 share a session (4+1=5), task 1 gets its own. Answer is 2.

The problem guarantees 1 is at most tasks[i] which is at most sessionTime. You do not need to handle the case where a single task exceeds sessionTime. But forgetting to check the "fits in current session" condition is a common bug. Always compare tasks[i] against remaining, not against sessionTime.

From understanding to recall

Bitmask DP has a reputation for being tricky, but the pattern is actually very consistent. The hard part is not the code. It is remembering to reach for this approach when you see a small n with subset-like constraints.

The next time you see a problem with n up to 14 or 15 and the state depends on which elements you have used, your first thought should be "bitmask DP." That reflex does not come from reading one blog post. It comes from seeing the pattern multiple times at spaced intervals, writing the bitmask loop from scratch, and building the muscle memory for mask & (1 << i) and mask | (1 << i).

Spaced repetition is what turns "I have seen this before" into "I know exactly how to set this up." You drill the bitmask DP skeleton independently, and when a new problem like this one shows up, you recognize the shape instantly.

Build your bitmask DP intuition with CodeBricks

Subsets - The foundational bitmask enumeration problem. Understanding how to iterate over all subsets is a prerequisite for bitmask DP.
Combination Sum - Another problem about partitioning values to hit a target, solved with backtracking. The packing logic here has a similar flavor.
Decode Ways - A classic DP problem with compound transitions. Good practice for DP state design before tackling bitmask variants.

Try CodeBricks free