https://leetcode.com/problems/find-minimum-time-to-finish-all-jobs

Solution 1

Not the fastest solution in python, but I think it is clean and it is easy to estimate its complexity.

Let us try to answer the following question first: given basket : working time for each worker, question is if we can allocate workers in such way, that each of them spend <= basket time. For example, if we have jobs = [1, 2, 3, 5, 7], and basket = 8, then we can allocate workers as [1, 7], [3, 5], [2] and we need at least 3 workers here.

Let dfs(mask, basket) be function with parameters:

  1. mask is binary mask of already used jobs
  2. basket is how many time each of workers can spend
  3. Answer will be tuple of numbers: first one is minimum number of workers and second one is how much time last worker already spent.

Let us discuss, how this function works in more details:

  1. If mask = 0, then we can state that we need at least 1 worker and he spent 0 time.
  2. For each j in range(N), if we have this job inside bitmask, we look at all dfs(mask - (1 << j), basket). We need to add jub number j now. If it happen, that we can not allocate it to the last worker, we need to hire one more worker. If we can, we allocate job to him.
  3. Finaly, we return min over all possible last jobs we can make.

Why this is working. It is similar to Travelling Salesman Problem (TSP). It is also similar to problem 698 Partition to K Equal Sum Subsets. Idea is that it is always enough to have only bitmask of already visited jobs, not order.

So far we are able to answer question: given basket, how many workers we need to hire to finish all jobs. We need to find minimum value of basket, such that there will be k workers enough. Ideal choice here is binary search.

Complexity: we have 2^n masks and O(n) transitions from one mask, so complexity of one run of dfs for given basket is O(n*2^n). We run it O(log M) times, where M is sum of all jobs, so final time complexity is 2^n*n*log(M). Space complexity in given code is 2^n*log(M), which can be easily reduced to 2^n.

Further thought As far as I aware, there is also O(k*3^n) complexity solution, I will code it later, but I think it will give TLE in python. There are also a lot of dfs solution with different pruning techniques, that are pretty good and working 5-50 times faster, depending on how you prune, but will you be able to explain complexity of those solution to interviewer?

class Solution:
    def minimumTimeRequired(self, jobs, k):
        N = len(jobs)
        
        @lru_cache(None)
        def dfs(mask, basket):
            if mask == 0: return (1, 0)
            ans = (float("inf"), float("inf"))
            for j in range(N):
                if mask & (1<<j):
                    pieces, last = dfs(mask - (1 << j), basket)
                    full = (last + jobs[j] > basket)
                    ans = min(ans, (pieces + full, jobs[j] + (1-full)*last))  
            return ans 

        beg, end = max(jobs), sum(jobs)
        while beg < end:
            mid = (beg + end)//2
            if dfs((1<<N) - 1, mid)[0] >= k + 1:
                beg = mid + 1
            else:
                end = mid
        
        return beg

Solution 2

We can also work with submasks: let the state be mask of available jobs and k is index of person. Then each time when we choose new person we need to look at all possible submasks. However we need to be careful and use a bit of prunning: without it in python we will get TLE: we check if cost[submask] >= ret: continue, that is do early stopping if cost of submask is more than score of mask, we do not consider this option.

Complexity

Time complexity is O(3^n * m), space complexity is O(2^n * m).

Code

class Solution:
    def minimumTimeRequired(self, jobs, k):
        n = len(jobs)
        cost = [0]*(1<<n)
        for mask, j in product(range(1<<n), range(n)):
            cost[mask] += jobs[j] * ((mask >> j) & 1)
        
        @lru_cache(None)
        def dp(mask, k):
            if k == 1:
                return cost[mask]
            submask, ret = mask, cost[mask]
            while (submask-1) & mask:
                submask = (submask-1) & mask
                if cost[submask] >= ret: continue
                ret = min(ret, max(cost[submask], dp(mask^submask, k-1)))
                
            return ret
        
        return dp((1<<n) - 1, k)

If you like the solution, you can upvote it on leetcode discussion section: Problem 1723