[数据结构与算法]Leetcode 1723. Find Minimum Time to Finish All Jobs [Python]

这题如果用朴素的backtracking 就TLE了（朴素如下）

class Solution:
    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
        N = len(jobs)
        jobs.sort(reverse = True)
        assign = [0 for _ in range(k)]
        self.res = float('inf')
        def backtracking(jobindex):
            if jobindex == N:
                self.res = min(self.res, max(assign))
                return
            for i in range(k):
                assign[i] += jobs[jobindex]
                backtracking(jobindex + 1)
                assign[i] -= jobs[jobindex]
            return
        backtracking(0)
        return self.res 

那么其实可以优化的是，每当更新出了全局最优self.res的时候，就可以拿来做pruning操作。以及，一个工人第一次被分配某一个工作后，剩下的backtracking过程都可以基于这个第一次被分配到的工作往下增加其他工作，而不用再次从0分配起。这样会重复计算。mod版本如下：

class Solution:
    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
        N = len(jobs)
        jobs.sort(reverse = True)
        assign = [0 for _ in range(k)]
        self.res = float('inf')
        def backtracking(jobindex):
            if jobindex == N:
                self.res = min(self.res, max(assign))
                return
            for i in range(k):
                if assign[i] + jobs[jobindex] < self.res:
                    assign[i] += jobs[jobindex]
                    backtracking(jobindex + 1)
                    assign[i] -= jobs[jobindex]
                if assign[i] == 0:
                    return
            return 
        backtracking(0)
        return self.res