Minimum Number of Work Sessions to Finish the Tasks
MedPrompt
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.length1 <= n <= 141 <= tasks[i] <= 10max(tasks[i]) <= sessionTime <= 15
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a brute-force recursive strategy to explore all possible ways of assigning tasks to work sessions. It tries to place each task one by one, either into an existing session or by starting a new one. The search space is pruned by keeping track of the minimum number of sessions found so far and abandoning paths that cannot yield a better result.
Algorithm
- The core of the approach is a recursive function, let's call it
dfs(taskIndex, sessionCount, sessions), wheretaskIndexis the index of the current task to assign,sessionCountis the number of sessions currently in use, andsessionsis an array storing the time consumed in each session. - A global variable,
minSessions, is used to keep track of the minimum number of sessions found so far, initialized to a large value (e.g.,n). - Base Case: When
taskIndexreachesn, it means all tasks have been assigned. We then updateminSessionswith the currentsessionCountif it's smaller. - Pruning: Before proceeding, the function checks if
sessionCountis already greater than or equal tominSessions. If so, this path cannot lead to a better solution, and the function returns immediately. - Recursive Step: For the current task
tasks[taskIndex], we explore two possibilities:- Assign to an existing session: Iterate through the
sessionCountactive sessions. If the current task fits into sessioni(i.e.,sessions[i] + tasks[taskIndex] <= sessionTime), place it there, and make a recursive calldfs(taskIndex + 1, sessionCount, sessions). After the call returns, backtrack by removing the task from the session. - Start a new session: Place the current task into a new session
sessionCount. Make a recursive calldfs(taskIndex + 1, sessionCount + 1, sessions). Backtrack after the call.
- Assign to an existing session: Iterate through the
- To potentially improve performance through better pruning, the
tasksarray can be sorted in descending order before starting the recursion. This heuristic places larger, more restrictive tasks first.
Walkthrough
The backtracking algorithm systematically generates all valid partitions of tasks into sessions. We define a recursive function that takes the index of the current task to be placed and the state of the current sessions (how much time is used in each).
For each task, we try to fit it into any of the already started sessions. If it fits, we add it and recurse for the next task. After returning, we backtrack by removing the task to explore other possibilities. If the task cannot fit in any existing session, or as another alternative, we can place it in a new session and recurse. This process continues until all tasks are placed. The minimum number of sessions used across all valid full assignments is the answer.
To make this more practical, we use pruning. We maintain a variable holding the minimum sessions found so far. If the number of sessions we are currently using already meets or exceeds this minimum, we know this path won't lead to a better solution, so we stop exploring it.
class Solution { private int minSessionsCount; private int[] tasks; private int n; private int sessionTime; public int minSessions(int[] tasks, int sessionTime) { this.tasks = tasks; this.n = tasks.length; this.sessionTime = sessionTime; this.minSessionsCount = n; // Worst case is one session per task int[] sessions = new int[n]; findMinSessions(0, 0, sessions); return minSessionsCount; } private void findMinSessions(int taskIndex, int currentSessionCount, int[] sessions) { // Pruning: If we already have more or equal sessions than the best found so far. if (currentSessionCount >= minSessionsCount) { return; } // Base case: All tasks have been assigned. if (taskIndex == n) { minSessionsCount = Math.min(minSessionsCount, currentSessionCount); return; } // Option 1: Assign the current task to an existing session. for (int i = 0; i < currentSessionCount; i++) { if (sessions[i] + tasks[taskIndex] <= sessionTime) { sessions[i] += tasks[taskIndex]; findMinSessions(taskIndex + 1, currentSessionCount, sessions); sessions[i] -= tasks[taskIndex]; // Backtrack } } // Option 2: Start a new session for the current task. sessions[currentSessionCount] = tasks[taskIndex]; findMinSessions(taskIndex + 1, currentSessionCount + 1, sessions); sessions[currentSessionCount] = 0; // Backtrack }}Complexity
Time
O(n * B_n), where B_n is the n-th Bell number. This is because we are exploring all partitions of the set of tasks. This is prohibitively slow for n=14.
Space
O(n), for the recursion depth and the `sessions` array.
Trade-offs
Pros
Conceptually straightforward and relatively easy to implement.
Uses minimal extra space, primarily for the recursion stack.
Cons
Extremely slow for the given constraints (
n <= 14) due to its exponential time complexity, which is related to Bell numbers.Likely to result in a 'Time Limit Exceeded' error on most competitive programming platforms.
Performance is highly dependent on the specific input values and the effectiveness of pruning.
This approach uses dynamic programming with bitmasking to find the optimal solution efficiently. The state of the DP is defined by a bitmask representing the subset of tasks that have been completed. For each subset, we compute the minimum number of sessions required and the time consumed in the last session.
Algorithm
- The state for our dynamic programming will be
dp[mask], which stores a pair of values:{numberOfSessions, timeOfLastSession}for the subset of tasks represented bymask. - A bitmask
maskis an integer where thei-th bit is 1 if thei-th task is included in the subset, and 0 otherwise. - The goal is to minimize
numberOfSessions, and as a tie-breaker, minimizetimeOfLastSessionto leave more capacity for subsequent tasks. - The
dptable of size2^nis initialized.dp[0]is the base case, representing zero tasks. We can set it to{0, sessionTime + 1}. This indicates 0 sessions are used, and the 'last session' is considered full, which conveniently forces the first task to start a new session. - We iterate through all masks from 1 to
(1 << n) - 1. - For each
mask, we determine itsdpvalue by considering adding each taskipresent in themaskto the configuration ofprev_mask = mask ^ (1 << i). - Let
(prevSessions, prevTime) = dp[prev_mask]. When addingtasks[i]:- If
prevTime + tasks[i] <= sessionTime, the task fits in the last session. The new state is{prevSessions, prevTime + tasks[i]}. - Otherwise, a new session must be started. The new state is
{prevSessions + 1, tasks[i]}.
- If
- We update
dp[mask]with the best state (minimum sessions, then minimum time) found by trying all tasksiin themask. - The final answer is the number of sessions stored in
dp[(1 << n) - 1].
Walkthrough
Given the constraint n <= 14, an exponential time complexity in n is acceptable. This suggests a solution involving bitmask DP. We can define a DP state dp[mask] that stores the optimal arrangement for the subset of tasks represented by the bitmask mask.
Specifically, dp[mask] will be a pair (numberOfSessions, timeUsedInLastSession). Our goal is to minimize numberOfSessions, and for an equal number of sessions, we want to minimize timeUsedInLastSession to maximize the chance of fitting more tasks into it.
We iterate through all possible masks from 1 up to 2^n - 1. For each mask, we compute its dp value by transitioning from smaller submasks. To compute dp[mask], we can try adding each task i (where the i-th bit is set in mask) to the optimal arrangement for the submask mask without task i (i.e., mask ^ (1 << i)). Based on the time left in the last session of the subproblem, we either add the current task to it or start a new session. We keep the best result among all choices for task i.
class Solution { public int minSessions(int[] tasks, int sessionTime) { int n = tasks.length; int numMasks = 1 << n; // dp[mask][0] = min sessions, dp[mask][1] = min time in last session int[][] dp = new int[numMasks][2]; for (int i = 1; i < numMasks; i++) { dp[i][0] = n + 1; // Initialize with a value larger than any possible answer dp[i][1] = sessionTime + 1; } // Base case: 0 tasks, 0 sessions. Time is set to be greater than sessionTime // so that the first task always starts a new session. dp[0][0] = 0; dp[0][1] = sessionTime + 1; for (int mask = 1; mask < numMasks; mask++) { for (int i = 0; i < n; i++) { // Check if task i is in the current subset (mask) if (((mask >> i) & 1) == 1) { int prevMask = mask ^ (1 << i); int prevSessions = dp[prevMask][0]; int prevTime = dp[prevMask][1]; int newSessions, newTime; if (prevTime + tasks[i] <= sessionTime) { // Add task i to the last session of the previous state newSessions = prevSessions; newTime = prevTime + tasks[i]; } else { // Start a new session for task i newSessions = prevSessions + 1; newTime = tasks[i]; } // If we found a better arrangement (fewer sessions, or same sessions with less time in the last one) if (newSessions < dp[mask][0] || (newSessions == dp[mask][0] && newTime < dp[mask][1])) { dp[mask][0] = newSessions; dp[mask][1] = newTime; } } } } return dp[numMasks - 1][0]; }}Complexity
Time
O(n * 2^n). We iterate through `2^n` masks, and for each mask, we iterate through `n` tasks.
Space
O(2^n) to store the DP table for all `2^n` masks.
Trade-offs
Pros
Guaranteed to find the minimum number of sessions.
Efficient enough to pass within the time limits for the given constraints.
Systematically builds the solution from smaller subproblems to larger ones.
Cons
Requires O(2^n) space, which can be substantial (e.g., for n=14, it's 16384 entries).
The logic for bitmask DP can be more complex to understand and implement correctly compared to a simple recursive solution.
Solutions
Solution
class Solution {public int minSessions(int[] tasks, int sessionTime) { int n = tasks.length; boolean[] ok = new boolean[1 << n]; for (int i = 1; i < 1 << n; ++i) { int t = 0; for (int j = 0; j < n; ++j) { if ((i >> j & 1) == 1) { t += tasks[j]; } } ok[i] = t <= sessionTime; } int[] f = new int[1 << n]; Arrays.fill(f, 1 << 30); f[0] = 0; for (int i = 1; i < 1 << n; ++i) { for (int j = i; j > 0; j = (j - 1) & i) { if (ok[j]) { f[i] = Math.min(f[i], f[i ^ j] + 1); } } } return f[(1 << n) - 1]; }}class Solution {public: int minSessions(vector<int> &tasks, int sessionTime) { int n = tasks.size(); bool ok[1 << n]; memset(ok, false, sizeof(ok)); for (int i = 1; i < 1 << n; ++i) { int t = 0; for (int j = 0; j < n; ++j) { if (i >> j & 1) { t += tasks[j]; } } ok[i] = t <= sessionTime; } int f[1 << n]; memset(f, 0x3f, sizeof(f)); f[0] = 0; for (int i = 1; i < 1 << n; ++i) { for (int j = i; j; j = (j - 1) & i) { if (ok[j]) { f[i] = min(f[i], f[i ^ j] + 1); } } } return f[(1 << n) - 1]; }};class Solution: def minSessions(self, tasks: List[int], sessionTime: int) -> int: n = len(tasks) ok = [False] * (1 << n) for i in range(1, 1 << n): t = sum(tasks[j] for j in range(n) if i >> j & 1) ok[i] = t <= sessionTime f = [inf] * (1 << n) f[0] = 0 for i in range(1, 1 << n): j = i while j: if ok[j]: f[i] = min(f[i], f[i ^ j] + 1) j = (j - 1) & i return f[- 1]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.