Watch 7 video solutions for Minimum Number of Work Sessions to Finish the Tasks, a medium level problem involving Array, Dynamic Programming, Backtracking. This walkthrough by Happy Coding has 5,477 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |