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:
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.length1 <= n <= 141 <= tasks[i] <= 10max(tasks[i]) <= sessionTime <= 15Problem 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.
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.
Time Complexity: O(n!) due to the permutations of tasks.
Space Complexity: O(n), for recursion stack and storing sessions.
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.
Python
C++
JavaScript
Time Complexity: O(2^n * n)
Space Complexity: O(2^n)
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(n!) due to the permutations of tasks. |
| Dynamic Programming with Bitmask | Time Complexity: O(2^n * n) |
| State Compression Dynamic Programming + Subset Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking | O(k^n) | O(n) | Useful for understanding the search process or when strong pruning significantly reduces states. |
| Dynamic Programming with Bitmask | O(n · 2^n) | O(2^n) | Best general solution when task count is small (≤14) and subset states can be encoded with bitmasks. |
LeetCode 1986. Minimum Number of Work Sessions to Finish the Tasks • Happy Coding • 5,477 views views
Watch 6 more video solutions →Practice Minimum Number of Work Sessions to Finish the Tasks with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor