DSA problem
Minimum Number of Work Sessions to Finish the Tasks
There are n tasks assigned to you. The task times are represented as an integer array tasks of length n, where the i-th 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, and you can start a new task immediately after finishing the previous one. Return the minimum number of work sessions needed to finish all the tasks following the conditions above.
Tasks cannot be split across sessions, so each task is dropped wholesale into some session whose used time plus the task's time does not exceed sessionTime. Because we can complete tasks in any order, the problem is really about partitioning the multiset of task durations into the minimum number of bins of capacity sessionTime.
With n up to 14, we cannot try every permutation, but we can iterate over every subset of tasks. The right state encodes which tasks have already been scheduled along with the remaining capacity of the currently open session. Two different completion orders that arrive at the same scheduled-set with the same open-session leftover capacity are interchangeable — they will both schedule the rest of the tasks identically.
The optimal formulation defines dp[mask] as a pair (sessions, currentSessionRemaining) describing the best schedule of the tasks in mask: sessions is the total session count used, and currentSessionRemaining is the unused time still available in the active session. "Best" means: minimize sessions first, then maximize currentSessionRemaining (so that future tasks have more room before forcing a new session). For each mask we extend it by every unscheduled task i; if tasks[i] fits in the current remaining time we extend the same session, otherwise we open a new session. Total time is O(2^n * n) and space O(2^n).
Examples
tasks = [1,2,3], sessionTime = 32tasks = [3,1,3,1,1], sessionTime = 81tasks = [1,2,3,4,5], sessionTime = 151Constraints
- n == tasks.length
- 1 <= n <= 14
- 1 <= tasks[i] <= 10
- max(tasks[i]) <= sessionTime <= 15
- It is guaranteed that every task fits inside one session.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.