Find Minimum Time to Finish All Jobs LeetCode solution in Python

1
class Solution:
2
    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
3
        def branchAndBound(i: int):
4
            nonlocal r
5
            if i == n:
6
                r = min(r, max(a))
7
                return
8
            visited = set()
9
            for j in range(k):
10
                if a[j] in visited:
11
                    continue
12
                visited.add(a[j])
13
                if a[j] + jobs[i] >= r:
14
                    continue
15
                a[j] += jobs[i]
16
                branchAndBound(i + 1)
17
                a[j] -= jobs[i]
18

19
        n = len(jobs)
20
        if n <= k:
21
            return max(jobs)
22

23
        # use greed algorithm to get upper bound
24
        jobs.sort(reverse=True)
25
        a = list(jobs[:k])
26
        for job in jobs[k:]:
27
            m0 = min(a)
28
            i = a.index(m0)
29
            a[i] += job
30
        r = max(a)
31

32
        a = [0] * k
33
        branchAndBound(0)
34
        return r