Skip to main content
Talentd

Minimum Number of Work Sessions to Finish the Tasks - Solution & Explanation

MediumArrayDynamic ProgrammingBacktrackingBit Manipulation14 min readAsked at: Amazon, Swiggy
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You get an array tasks where each value represents the time needed to finish a task. Each work session has a maximum duration sessionTime. Tasks cannot be split across sessions. The goal is to schedule tasks so that the total number of sessions used is minimized.

Approach 1: Backtracking (Exponential Time)

This approach tries to assign every task to an existing session or start a new one. Maintain a list representing the remaining time in each session and recursively place tasks one by one. If a task fits in an existing session, reduce that session's remaining time and continue; otherwise open a new session. Pruning helps reduce the search space by skipping equivalent states when sessions have identical remaining capacity. The time complexity is O(k^n) in the worst case (where k is the number of sessions explored) with O(n) recursion space. This approach is intuitive and demonstrates the scheduling logic clearly, but it does not scale well when the number of tasks grows.

Approach 2: Dynamic Programming with Bitmask (O(n · 2^n))

The optimal strategy models each subset of tasks as a bitmask. Let dp[mask] represent the minimum number of sessions needed to complete the tasks included in mask. For each mask, try adding one more task that is not yet included. Track both the number of sessions used and the remaining time in the current session. If the new task fits in the current session, update the remaining time; otherwise start a new session. Because there are 2^n subsets and up to n transitions per state, the total time complexity is O(n · 2^n) with O(2^n) space. Bitmasking keeps the state compact and makes subset transitions efficient. This technique is common in problems involving small n and subset optimization.

Both approaches rely on exploring combinations of tasks, which connects directly to backtracking, dynamic programming, and bitmask state compression patterns often used in scheduling and subset problems.

Recommended for interviews: The Dynamic Programming with Bitmask approach. Interviewers expect you to recognize that n ≤ 14 enables subset DP. A quick brute-force/backtracking idea shows you understand the search space, but implementing the O(n · 2^n) bitmask DP demonstrates stronger algorithmic maturity and optimization skills.

Approach 1: Backtracking Approach

The backtracking approach involves attempting to distribute tasks into sessions recursively. If a configuration is not feasible, the algorithm backtracks and tries another configuration. This approach ensures that we try all possible ways to allocate tasks to the least number of sessions.

This solution uses a backtracking method where we try to fit each task into existing sessions. If a session can't take the task, we make a new session. We continue this way, trying all possibilities, ensuring we backtrack when exceeding feasible solutions.

Code

PythonC++Java

Python

C++

Java

Complexity

Time Complexity: O(n!) due to the permutations of tasks.
Space Complexity: O(n), for recursion stack and storing sessions.

Try this approach in the editor →

Approach 2: Dynamic Programming with Bitmask

This approach leverages dynamic programming along with bit masking to efficiently explore all task combinations and manage them with a state and subproblem strategy.

This Python implementation uses dynamic programming and bitmasking to track the state of task completion. We recursively evaluate adding tasks to current sessions or starting new sessions based on already taken tasks represented in binary form.

Code

PythonC++JavaScript

Python

C++

JavaScript

Complexity

Time Complexity: O(2^n * n)
Space Complexity: O(2^n)

Try this approach in the editor →

Approach 3: State Compression Dynamic Programming + Subset Enumeration

We note that n does not exceed 14, so we can consider using state compression dynamic programming to solve this problem.

We use a binary number i of length n to represent the current task state, where the j-th bit of i is 1 if and only if the j-th task is completed. We use f[i] to represent the minimum number of work sessions needed to complete all tasks with state i.

We can enumerate all subsets j of i, where each bit of the binary representation of j is a subset of the corresponding bit of the binary representation of i, i.e., j \subseteq i. If the tasks corresponding to j can be completed in one work session, then we can update f[i] using f[i \oplus j] + 1, where i \oplus j represents the bitwise XOR of i and j.

The final answer is f[2^n - 1].

The time complexity is O(n times 3^n), and the space complexity is O(2^n). Here, n is the number of tasks.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking Approach

Time Complexity: O(n!) due to the permutations of tasks.
Space Complexity: O(n), for recursion stack and storing sessions.

Dynamic Programming with Bitmask

Time Complexity: O(2^n * n)
Space Complexity: O(2^n)

State Compression Dynamic Programming + Subset Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BacktrackingO(k^n)O(n)Useful for understanding the search process or when strong pruning significantly reduces states.
Dynamic Programming with BitmaskO(n · 2^n)O(2^n)Best general solution when task count is small (≤14) and subset states can be encoded with bitmasks.

Video Solution

LeetCode 1986. Minimum Number of Work Sessions to Finish the Tasks • Happy Coding • 5,663 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Minimum Number of Work Sessions to Finish the Tasks easy or hard?
The problem is rated Medium on LeetCode but feels closer to Medium-Hard for many candidates. Recognizing that the task count allows subset dynamic programming is the key insight. Once the bitmask state representation is identified, the implementation becomes manageable.
Minimum Number of Work Sessions to Finish the Tasks Python/Java solution
Most implementations use either backtracking with pruning or dynamic programming with bitmasks. Python solutions typically store DP states in arrays or dictionaries, while Java or C++ versions use integer bitmasks and arrays for fast transitions. The optimal implementations run in O(n · 2^n) time.
How to solve Minimum Number of Work Sessions to Finish the Tasks in O(n · 2^n)?
Use bitmask dynamic programming where each mask represents a subset of completed tasks. Store the minimum sessions used and the remaining time in the current session for that subset. When adding a new task, either fit it into the current session or start a new one. Iterating over all masks yields O(n · 2^n) time complexity.
What is the best approach for Minimum Number of Work Sessions to Finish the Tasks?
Dynamic Programming with Bitmask is the most efficient approach. Each subset of tasks is represented by a bitmask, and the algorithm tracks the minimum sessions needed while keeping remaining time in the current session. The complexity is O(n · 2^n) time and O(2^n) space, which works well because the number of tasks is small.
Is Minimum Number of Work Sessions to Finish the Tasks asked at Google/Amazon/Meta?
This problem represents a classic subset scheduling and state-compression pattern commonly used in technical interviews at large tech companies. Variants involving task scheduling, bitmask DP, or subset optimization frequently appear in interviews at companies like Google, Amazon, and Meta.
What data structure is used in Minimum Number of Work Sessions to Finish the Tasks?
The key technique uses a bitmask to represent subsets of tasks combined with a dynamic programming array or hash table. Each state tracks the number of sessions and remaining session time. Recursion with arrays or lists is also used in the backtracking version.
What is the time complexity of Minimum Number of Work Sessions to Finish the Tasks?
The optimal solution using bitmask dynamic programming runs in O(n · 2^n) time with O(2^n) space. The algorithm iterates over every subset of tasks and tries adding one additional task to update the state. A pure backtracking approach can degrade to exponential time such as O(k^n).

Ready to solve this problem?

Practice Minimum Number of Work Sessions to Finish the Tasks with our built-in code editor and test cases.

Practice on FleetCode
Previous

Fair Distribution of Cookies

Next

Find Minimum Time to Finish All Jobs