find-minimum-time-to-finish-all-jobs.py

# Time:  O(k^n * logr), the real complexity shoud be much less, but hard to analyze
# Space: O(n + k)

class Solution(object):
    def minimumTimeRequired(self, jobs, k):
        """
        :type jobs: List[int]
        :type k: int
        :rtype: int
        """
        def backtracking(jobs, i, cap, counts):
            if i == len(jobs):
                return True
            for j in xrange(len(counts)):
                if counts[j]+jobs[i] <= cap:
                    counts[j] += jobs[i]
                    if backtracking(jobs, i+1, cap, counts):
                        return True
                    counts[j] -= jobs[i]
                if counts[j] == 0:
                    break
            return False

        jobs.sort(reverse=True)
        left, right = max(jobs), sum(jobs)
        while left <= right:
            mid = left + (right-left)//2
            if backtracking(jobs, 0, mid, [0]*k):
                right = mid-1
            else:
                left = mid+1
        return left


# Time:  O(k * k^n), the real complexity shoud be less, but hard to analyze
# Space: O(n + k)
class Solution2(object):
    def minimumTimeRequired(self, jobs, k):
        """
        :type jobs: List[int]
        :type k: int
        :rtype: int
        """
        def backtracking(jobs, i, counts, result):
            if i == len(jobs):
                result[0] = min(result[0], max(counts))
                return
            for j in xrange(len(counts)):
                if counts[j]+jobs[i] <= result[0]:
                    counts[j] += jobs[i]
                    backtracking(jobs, i+1, counts, result)
                    counts[j] -= jobs[i]
                if counts[j] == 0:
                    break

        jobs.sort(reverse=False)
        result = [sum(jobs)]
        backtracking(jobs, 0, [0]*k, result)
        return result[0]