Minimum Number of Work Sessions to Finish the Tasks
Problem Description
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
Solve it on LeetCode
Approaches
1. Backtracking
In this approach, we will use simple backtracking. The basic idea is to try all possible ways to assign tasks to work sessions and keep track of the minimum number of sessions needed.
Intuition:
- We initially start with an empty assignment of tasks to work sessions.
- For each task, we have several options:
- Start a new session and assign the task to this session.
- Assign the task to an existing session if its duration plus this task's duration does not exceed the session's limit.
- We explore all possibilities using backtracking, and at each step, we attempt to assign a task either to a new session or a suitable existing session.
- Base Case: When all the tasks are assigned, count the number of sessions used and record the result if it's the minimum so far.
Code:
- Time Complexity: O(n!), where n is the number of tasks. This is because of all the possible permutations of task assignments.
- Space Complexity: O(n), for the recursive call stack and additional space used by the
sessions.
2. Dynamic Programming with State Compression
This approach improves efficiency by using dynamic programming combined with bitmasking to represent task assignments in sessions.
Intuition:
- Use a bitmask to represent subsets of tasks and dynamic programming to store the minimum sessions required for each subset.
- For a given state (submask of tasks), split it into two parts representing assignments to two different groups of sessions.
- Calculate the minimum sessions required for each group and update the state.
- Iterate all subsets and use previously computed results to find the minimum sessions needed.
Code:
- Time Complexity: O(2^n * n), where n is the number of tasks. Each state is visited, and for each state, we explore its subsets.
- Space Complexity: O(2^n), for storing results of each submask in the dynamic programming array.