LeetCode 1986 - Minimum Number of Work Sessions to Finish the Tasks

LeetCode Problem 1986

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Backtracking, Bit Manipulation, Bitmask

Solution

Problem Understanding

This problem asks us to schedule a collection of tasks into the minimum number of work sessions. Each task has a fixed duration, and every work session has a maximum allowed length, sessionTime.

A task cannot be split across multiple sessions. Once a task starts inside a session, it must fully complete within that same session. However, tasks may be performed in any order, which means we are free to rearrange them to achieve a better packing strategy.

The input consists of:

• tasks, an array where tasks[i] is the duration of the i-th task
• sessionTime, the maximum number of hours allowed in a single session

The output is a single integer representing the minimum number of sessions required to complete all tasks.

The constraints are extremely important here:

• n <= 14
• sessionTime <= 15

The small value of n strongly suggests that exponential algorithms involving subsets or bitmasks are acceptable. In fact, 2^14 = 16384, which is small enough for dynamic programming over subsets.

Several edge cases are worth identifying immediately.

If all tasks fit into one session, the answer is simply 1. If every task is exactly equal to sessionTime, then each task requires its own session. Another important case is when many small tasks can be combined in different ways, because greedy packing strategies may fail to find the true optimum.

For example:

tasks = [1,2,3,4]
sessionTime = 5

A naive greedy strategy might place 4 alone, then 3+2, then 1, using 3 sessions. But the optimal arrangement is 4+1 and 3+2, which only needs 2 sessions.

This means we need a globally optimal strategy rather than a local greedy choice.

Approaches

Brute Force Approach

A brute force solution would try every possible ordering of tasks and simulate placing tasks into sessions. Since tasks can appear in any order, there are n! permutations.

For each ordering, we could greedily pack tasks into sessions and compute how many sessions are needed. We would then take the minimum across all permutations.

This approach is correct because it explores every possible arrangement of tasks. Eventually, it will discover the optimal scheduling.

However, the time complexity is far too large. Even for n = 14, the number of permutations is:

14! ≈ 87 billion

This is completely infeasible.

We need a more efficient way to represent states and avoid recomputing equivalent subproblems.

Key Insight

The important observation is that the actual order of tasks inside a session does not matter. What matters is only:

1. Which tasks have already been completed
2. How much space remains in the current session

This naturally leads to dynamic programming with bitmasking.

A bitmask can represent the set of completed tasks:

• Bit i = 1 means task i is already completed
• Bit i = 0 means task i is still unfinished

Since n <= 14, every subset of tasks can be represented using an integer from 0 to (1 << n) - 1.

Instead of tracking only the minimum number of sessions, we also track the remaining time in the current session. This is crucial because two states with the same number of sessions may have different future potential.

For example:

2 sessions used, 4 hours remaining

is better than:

2 sessions used, 1 hour remaining

because the first state can fit more future tasks.

We therefore use dynamic programming where each subset stores:

(sessions_used, remaining_time)

and we always prefer:

• fewer sessions
• if sessions tie, larger remaining time

This gives an optimal exponential-time solution that is efficient enough for the constraints.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! × n)	O(n)	Tries every task ordering
Optimal Bitmask DP	O(n × 2^n)	O(2^n)	Dynamic programming over subsets

Algorithm Walkthrough

Step 1: Represent task subsets using bitmasks

We use an integer mask where each bit represents whether a task has already been completed.

For example:

tasks = [1,2,3]
mask = 101₂

means tasks 0 and 2 are completed.

The final goal state is:

(1 << n) - 1

where all bits are set.

Step 2: Define the DP state

For each subset mask, we store:

dp[mask] = (sessions_used, remaining_time)

This represents the optimal way to complete exactly the tasks in mask.

We compare states lexicographically:

1. Smaller session count is better
2. If session counts tie, larger remaining time is better

This second condition is important because more remaining time gives greater flexibility for future tasks.

Step 3: Initialize the base case

Initially, no tasks are completed:

mask = 0

We start with one empty session available:

dp[0] = (1, sessionTime)

This means:

• we are currently using 1 session
• the entire session is still unused

Step 4: Transition to new states

For every current subset mask, we try adding each unfinished task.

Suppose:

task_time = tasks[i]

There are two possibilities.

Case 1: Task fits in current session

If:

remaining_time >= task_time

then we place the task into the current session:

new_state = (
    sessions_used,
    remaining_time - task_time
)

Case 2: Task does not fit

Otherwise, we must start a new session:

new_state = (
    sessions_used + 1,
    sessionTime - task_time
)

We update the target subset:

new_mask = mask | (1 << i)

If the new state is better than the currently stored state, we replace it.

Step 5: Continue until all subsets are processed

We iterate through every mask from:

0 to (1 << n) - 1

and process all transitions.

Step 6: Return the final answer

The answer is:

dp[(1 << n) - 1][0]

which is the minimum number of sessions needed to complete all tasks.

Why it works

The DP explores every possible subset of completed tasks and every valid way to extend those subsets. Because each transition either places a task into the current session or starts a new session, every legal schedule is represented.

The DP always keeps the optimal state for each subset according to:

1. minimum sessions
2. maximum remaining time

Therefore, no better future schedule can be lost, and the final state for the full mask is guaranteed to be optimal.

Python Solution

from typing import List

class Solution:
    def minSessions(self, tasks: List[int], sessionTime: int) -> int:
        n = len(tasks)
        total_masks = 1 << n

        # dp[mask] = (sessions_used, remaining_time)
        dp = [(float("inf"), -1)] * total_masks
        dp[0] = (1, sessionTime)

        for mask in range(total_masks):
            sessions_used, remaining_time = dp[mask]

            for i in range(n):
                if mask & (1 << i):
                    continue

                task_time = tasks[i]
                next_mask = mask | (1 << i)

                # Task fits in current session
                if remaining_time >= task_time:
                    candidate = (
                        sessions_used,
                        remaining_time - task_time
                    )
                else:
                    # Start new session
                    candidate = (
                        sessions_used + 1,
                        sessionTime - task_time
                    )

                current = dp[next_mask]

                # Better if fewer sessions,
                # or same sessions with more remaining time
                if (
                    candidate[0] < current[0]
                    or (
                        candidate[0] == current[0]
                        and candidate[1] > current[1]
                    )
                ):
                    dp[next_mask] = candidate

        full_mask = total_masks - 1
        return dp[full_mask][0]

The implementation begins by computing the total number of subsets:

1 << n

Each subset is represented as a bitmask.

The dp array stores tuples:

(sessions_used, remaining_time)

Initially:

dp[0] = (1, sessionTime)

because no tasks are completed yet and the first session is entirely free.

The outer loop iterates through all subsets. For every subset, the inner loop tries adding each unfinished task.

The condition:

if mask & (1 << i):

checks whether task i is already completed.

When adding a task, the algorithm determines whether the task fits in the current session. If it does, the remaining time decreases. Otherwise, a new session is started.

The update logic ensures that the DP always stores the best state for each subset. Fewer sessions are always preferred, and if session counts tie, the state with more remaining capacity is kept.

Finally, the answer is retrieved from the subset where all tasks are completed.

Go Solution

package main

import "math"

func minSessions(tasks []int, sessionTime int) int {
	n := len(tasks)
	totalMasks := 1 << n

	type State struct {
		sessions int
		remaining int
	}

	dp := make([]State, totalMasks)

	for i := 0; i < totalMasks; i++ {
		dp[i] = State{
			sessions: math.MaxInt32,
			remaining: -1,
		}
	}

	dp[0] = State{
		sessions: 1,
		remaining: sessionTime,
	}

	for mask := 0; mask < totalMasks; mask++ {
		current := dp[mask]

		for i := 0; i < n; i++ {
			if (mask & (1 << i)) != 0 {
				continue
			}

			taskTime := tasks[i]
			nextMask := mask | (1 << i)

			var candidate State

			if current.remaining >= taskTime {
				candidate = State{
					sessions: current.sessions,
					remaining: current.remaining - taskTime,
				}
			} else {
				candidate = State{
					sessions: current.sessions + 1,
					remaining: sessionTime - taskTime,
				}
			}

			best := dp[nextMask]

			if candidate.sessions < best.sessions ||
				(candidate.sessions == best.sessions &&
					candidate.remaining > best.remaining) {
				dp[nextMask] = candidate
			}
		}
	}

	fullMask := totalMasks - 1
	return dp[fullMask].sessions
}

The Go implementation follows the exact same logic as the Python version. Since Go does not support tuple comparison directly, a custom State struct is used to store:

sessions
remaining

The DP array is initialized with very large session counts using:

math.MaxInt32

Go slices are used instead of Python lists, but the subset transition logic remains identical.

No special handling for integer overflow is required because all values are extremely small under the problem constraints.

Worked Examples

Example 1

tasks = [1,2,3]
sessionTime = 3

Initial State

Mask	Completed Tasks	DP State
000	none	(1, 3)

Processing mask = 000

Try adding task 0:

remaining = 3
task = 1

Fits in current session.

dp[001] = (1, 2)

Try adding task 1:

dp[010] = (1, 1)

Try adding task 2:

dp[100] = (1, 0)

Processing mask = 001

Current state:

(1, 2)

Add task 1:

2 fits
remaining = 0

dp[011] = (1, 0)

Add task 2:

3 does not fit

Start new session:

dp[101] = (2, 0)

Processing mask = 011

Current state:

(1, 0)

Add task 2:

No space left

Start new session:

dp[111] = (2, 0)

Final answer:

2

Example 2

tasks = [3,1,3,1,1]
sessionTime = 8

One optimal packing is:

3 + 1 + 3 + 1 = 8
1

The DP eventually reaches:

all tasks completed -> (2, 7)

meaning:

• 2 sessions used
• 7 unused hours left in the final session

Answer:

2

Example 3

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

Total sum:

1 + 2 + 3 + 4 + 5 = 15

Every task fits into a single session.

The DP repeatedly places tasks into the current session without ever opening a new one.

Final state:

(1, 0)

Answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × 2^n)	Each subset tries adding every task
Space	O(2^n)	DP table stores one state per subset

There are 2^n possible subsets of tasks. For every subset, we iterate through all n tasks to determine which unfinished task to add next.

Since n <= 14, the total number of operations is manageable:

14 × 16384 ≈ 229,376

which easily fits within time limits.

The space usage comes from the DP table containing one entry per subset.

Test Cases

sol = Solution()

# Provided examples
assert sol.minSessions([1,2,3], 3) == 2  # basic example
assert sol.minSessions([3,1,3,1,1], 8) == 2  # packing optimization
assert sol.minSessions([1,2,3,4,5], 15) == 1  # all tasks fit

# Single task
assert sol.minSessions([5], 5) == 1  # exactly fills one session

# Every task requires its own session
assert sol.minSessions([5,5,5], 5) == 3  # no combining possible

# Multiple perfect pairings
assert sol.minSessions([1,4,2,3], 5) == 2  # optimal grouping

# Greedy would fail here
assert sol.minSessions([1,2,3,4], 5) == 2  # requires careful packing

# Many small tasks
assert sol.minSessions([1,1,1,1,1,1], 3) == 2  # combine efficiently

# Maximum constraints style case
assert sol.minSessions([10] * 14, 10) == 14  # each task isolated

# Tasks with leftover space
assert sol.minSessions([2,2,2,2], 3) == 4  # cannot pair

# Exact packing
assert sol.minSessions([2,2,2,2], 4) == 2  # perfect pairing

# Uneven packing
assert sol.minSessions([7,3,2,2], 8) == 2  # optimal rearrangement

print("All tests passed!")

Test Case Summary

Test	Why
[1,2,3], 3	Basic functionality
[3,1,3,1,1], 8	Non-trivial packing
[1,2,3,4,5], 15	Everything fits in one session
[5], 5	Smallest valid input
[5,5,5], 5	Every task isolated
[1,4,2,3], 5	Perfect pairing scenario
[1,2,3,4], 5	Greedy counterexample
[1,1,1,1,1,1], 3	Many small tasks
[10] * 14, 10	Near maximum constraint
[2,2,2,2], 3	No tasks combine
[2,2,2,2], 4	Exact session packing
[7,3,2,2], 8	Requires careful arrangement

Edge Cases

One important edge case occurs when all tasks already fit into a single session. In this situation, the optimal answer should be 1. Some incorrect implementations may unnecessarily create extra sessions because they initialize the DP incorrectly or fail to reuse remaining capacity properly. This implementation handles the case naturally because tasks continue being added to the current session as long as enough remaining time exists.

Another important edge case is when every task exactly equals sessionTime. Since no two tasks can share a session, the answer must equal the number of tasks. Bugs often occur when implementations accidentally allow sessions to exceed the limit or incorrectly merge tasks. The transition logic here strictly checks:

remaining_time >= task_time

before placing a task into the current session.

A third subtle edge case involves states with the same number of sessions but different remaining capacities. For example:

(2 sessions, 4 remaining)

is strictly better than:

(2 sessions, 1 remaining)

because future tasks are easier to place. If an implementation stores only the minimum session count, it may discard better future possibilities and produce incorrect results. This solution correctly keeps the state with larger remaining capacity whenever session counts tie.

A final important edge case is the maximum constraint size:

n = 14

A naive recursive search without memoization can become extremely slow due to repeated subproblems. The bitmask DP avoids this by solving each subset exactly once, ensuring efficient performance even at the upper limit.