1723. Find Minimum Time to Finish All Jobs

Solution 1: backtracking + branch pruning

Time complexity: O (N ^ K) since each job has K options. Can be converted to O(K ^ N) (i.e, find out all jobs should be sent to worker[0], then find out all jobs that should be sent to worker[1]...)

my initial solution got TLE

class Solution:
    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
        def helper(cur_idx, times):
            if cur_idx == len(jobs):
                return max(times)
            
            min_time = float("inf")
            for i in range(k):
                times[i] += jobs[cur_idx]
                min_time = min(min_time, helper(cur_idx+1, times))
                times[i] -= jobs[cur_idx]
            return min_time
        
        times = [0] * k
        return helper(0, times)

2 branch-pruning techniques:

use self.res to record current best answer and stop searching if the search result is clearly to be worse than current best answer
use a set to record processed subset. This comment explains it well: Filtering out the searched value is really useful, and interestingly, this is actually a common technique in discrete optimization, where it's called Symmetry Breaking. Basically, for +x operation, workers = [10, 5+x, 5, 5, 5, 5, 5, 5, 5, 5] is considered symmetric to workers = [10, 5, 5+x, 5, 5, 5, 5, 5, 5, 5] or any 5s, so we only try one of them.

class Solution:
    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
        self.res = float("inf")
        
        def helper(cur_idx):
            if cur_idx == len(jobs):
                self.res = min(self.res, max(times))
                return
            
            seen = set()
            for i in range(k):
                if times[i] not in seen:
                    seen.add(times[i])
                    times[i] += jobs[cur_idx]
                    if times[i] < self.res:
                        helper(cur_idx+1)
                    times[i] -= jobs[cur_idx]
            return
        
        times = [0] * k
        helper(0)
        return self.res

1723. Find Minimum Time to Finish All Jobs - cocoder39/coco39_LC GitHub Wiki