#1986

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Number of Work Sessions to Finish the Tasks

Find the minimum number of work sessions needed to finish a set of tasks, considering task durations and session time.

array dynamic programming backtracking bit manipulation bitmask

Problem Statement

You are given an array of tasks, where each element represents the time in hours required to complete a specific task. You are also given a session time, which dictates the maximum number of consecutive hours you can work in a single work session. Your goal is to finish all the tasks with the minimum number of work sessions, ensuring each session doesn’t exceed the session time limit.

Return the minimum number of work sessions required to finish all tasks while respecting the session time constraint. This problem can be solved using state transition dynamic programming, where we explore all combinations of task assignments and check if they fit within the session time limit.

Examples

Example 1

Input: tasks = [1,2,3], sessionTime = 3

Output: 2

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

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

You can finish all the tasks in one work session.

Constraints

n == tasks.length
1 <= n <= 14
1 <= tasks[i] <= 10
max(tasks[i]) <= sessionTime <= 15

Solution Approach

State Transition Dynamic Programming

Utilize dynamic programming to represent the state of tasks that have been assigned to a session. By using bitmasking to track the assigned tasks, you can recursively calculate the minimum work sessions required by trying all combinations of task assignments and checking if they fit within the session time limit.

Backtracking with Bitmasking

Leverage backtracking with bitmasking to efficiently explore all task combinations and assign them to work sessions. This method helps prune invalid configurations and avoid redundant calculations while ensuring that the task combinations respect the session time constraint.

Memoization to Optimize Recursion

Apply memoization to store previously computed results for specific task combinations to avoid recalculating the same configuration multiple times. This significantly reduces computation time and makes the solution more efficient.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of subsets of tasks, which is 2^n, where n is the number of tasks. The space complexity depends on the memoization table, which stores results for each subset of tasks, making it O(2^n).

What Interviewers Usually Probe

Look for understanding of bitmasking and dynamic programming principles.
Assess the candidate’s ability to optimize recursive solutions using memoization.
Evaluate how well the candidate can balance brute force and optimization techniques.

Common Pitfalls or Variants

Common pitfalls

Failing to properly handle all combinations of task assignments within the session time.
Not using bitmasking effectively to track which tasks have been assigned.
Overlooking the importance of memoization, leading to redundant calculations and slower performance.

Follow-up variants

Increase the maximum number of tasks or change the session time limit to test scalability.
Use this problem as a foundation to solve similar problems involving scheduling and task assignments.
Modify the problem to include different task durations and session time constraints.

FAQ

How does state transition dynamic programming apply to this problem?

State transition dynamic programming uses a bitmask to represent the set of tasks completed so far, allowing you to efficiently calculate the minimum work sessions needed.

What is bitmasking, and why is it important for this problem?

Bitmasking is a technique used to represent subsets of tasks in a compact form. It helps track which tasks have been assigned and ensures efficient calculation of task combinations.

Can I solve the "Minimum Number of Work Sessions to Finish the Tasks" problem using a greedy approach?

A greedy approach would not guarantee the optimal solution because it may not always make the best choices at each step. Dynamic programming is better suited for this problem.

How do I avoid redundant calculations in this problem?

Use memoization to store the results of previously computed task assignments, preventing redundant recalculations and improving performance.

What is the time complexity of the solution?

The time complexity is O(2^n), where n is the number of tasks, as you need to explore all subsets of tasks to find the optimal solution.

terminal

Solution

Solution 1: State Compression Dynamic Programming + Subset Enumeration

We note that $n$ does not exceed $14$, so we can consider using state compression dynamic programming to solve this problem.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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]

Continue Practicing

#1947 maximum compatibility score sum #1799 maximize score after n operations #1723 find minimum time to finish all jobs