What is the time complexity of LeetCode 1986. Minimum Number of Work Sessions to Finish the Tasks?

The Python solution on this page runs in O(n \times 3^n).

What is the space complexity of LeetCode 1986. Minimum Number of Work Sessions to Finish the Tasks?

The Python solution on this page uses O(2^n) auxiliary space.

Minimum Number of Work Sessions to Finish the Tasks — LeetCode 1986 Python Solution

MediumBit ManipulationArrayDynamic ProgrammingBacktrackingBitmask

Problem: #1986
Pattern: Backtracking
Reading time: 3 min
Source: leetcode.com

The problem

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.

Example

Input: tasks = [1,2,3], sessionTime = 3
Output: 2
Explanation: You can finish the tasks in two work sessions.

Python solution

Python

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]

Complexity

Measure	Complexity
Time	O(n \times 3^n)
Space	O(2^n) auxiliary

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 1986. Minimum Number of Work Sessions to Finish the Tasks is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1986. Minimum Number of Work Sessions to Finish the Tasks?: LeetCode 1986. Minimum Number of Work Sessions to Finish the Tasks is rated Medium on LeetCode.
What is the time complexity of LeetCode 1986. Minimum Number of Work Sessions to Finish the Tasks?: The Python solution on this page runs in O(n \times 3^n).
What is the space complexity of LeetCode 1986. Minimum Number of Work Sessions to Finish the Tasks?: The Python solution on this page uses O(2^n) auxiliary space.
What topics does LeetCode 1986. Minimum Number of Work Sessions to Finish the Tasks cover?: LeetCode 1986. Minimum Number of Work Sessions to Finish the Tasks is tagged Bit Manipulation, Array, Dynamic Programming, Backtracking and Bitmask on LeetCode.