We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Work Sessions to Finish the Tasks

Number: 2114

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

You are given an array of tasks, where each task takes a certain amount of time to complete. You have sessions in which you can work for at most sessionTime hours. Tasks must be finished in the same session in which they are started, though tasks can be completed in any order. The goal is to determine the minimum number of work sessions required to finish all tasks.

Key Insights

  • Use bitmasking to represent the state of completed tasks since n ≤ 14.
  • Apply recursion with memoization (DP) to explore task assignments.
  • Each DP state is represented by a bitmask (indicating tasks done) and the current session’s used time.
  • When a task does not fit in the current session, start a new session and update the count.
  • The problem can be solved with backtracking combining DP over subsets of tasks.

Space and Time Complexity

Time Complexity: O(2^n * n), where n is the number of tasks. Space Complexity: O(2^n) due to memoization storage.

Solution

We use a dynamic programming approach with bitmasking to represent the subsets of tasks completed. The recursive function dp(mask, timeUsed) returns the number of extra sessions required (beyond an initial session) for a given state. For every state, we try assigning each incomplete task: if it fits into the current session (timeUsed + task[i] ≤ sessionTime), we continue; otherwise, we start a new session and add 1 to our count. By caching results of each state (mask, timeUsed), we prevent redundant calculations, which makes the approach feasible given the constraints.

Code Solutions

def minSessions(tasks, sessionTime):
    n = len(tasks)
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dp(mask, time_used):
        # Base condition: if all tasks are completed.
        if mask == (1 << n) - 1:
            return 0
        best = float('inf')
        for i in range(n):
            # If task i is not yet completed.
            if not (mask & (1 << i)):
                if time_used + tasks[i] <= sessionTime:
                    best = min(best, dp(mask | (1 << i), time_used + tasks[i]))
                else:
                    best = min(best, 1 + dp(mask | (1 << i), tasks[i]))
        return best

    # We start with one session and 0 time used.
    return 1 + dp(0, 0)

# Example Usage
print(minSessions([1,2,3], 3))       # Output: 2
print(minSessions([3,1,3,1,1], 8))     # Output: 2
print(minSessions([1,2,3,4,5], 15))    # Output: 1
← Back to All Questions