Problem statement

https://leetcode.com/problems/minimum-number-of-work-sessions-to-finish-the-tasks/

Solution

You can see that in this problem n <= 14, so we need to apply some kind of bruteforce algorithm. If we try just n! options, it will be too big, so the idea is to use dynamic programming on subsets. Let dp(mask), where mask is bitmask of already used jobs be the tuple of numbers: first one is number of sessions we took so far and the second one is how much time we spend for the last session.

To calculate dp(mask), let us say dp(10110), we need to look at all places we have 0, that is 1-th, 2-th, 4-th and look at positions dp(00110), dp(10010), dp(10100). We calculate full = last + tasks[j] > T is indicator that last session is full and we need to start new one. So, total number of sessions we have is pieces + full and what we have in the last session is tasks[j] if session is full: we start new one and tasks[j] + last if it is not full.

Complexity

Time complexity is O(2^n * n), because we have 2^n masks and O(n) transitions from given mask. Space complexity is O(2^n).

class Solution:
    def minSessions(self, tasks, T):
        n = len(tasks)

        @lru_cache(None)
        def dp(mask):
            if mask == 0: return (1, 0)
            ans = (float("inf"), float("inf"))
            for j in range(n):
                if mask & (1<<j):
                    pieces, last = dp(mask - (1 << j))
                    full = (last + tasks[j] > T)
                    ans = min(ans, (pieces + full, tasks[j] + (1-full)*last))  
            return ans

        return dp((1<<n) - 1)[0]