1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
# 1335. Minimum Difficulty of a Job Schedule
"""
You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work
on the ith job, you have to finish all the jobs j where 0 <= j < i).
You have to finish at least one task every day. The difficulty of a job schedule
is the sum of difficulties of each day of the d days. The difficulty of a day is
the maximum difficulty of a job done on that day.
You are given an integer array job_difficulty and an integer d. The difficulty of
the ith job is job_difficulty[i].
Return the minimum difficulty of a job schedule. If you cannot find a schedule
for the jobs return -1.
"""
class Solution(object):
def helper(self, job_difficulty, days_left, idx):
n = len(job_difficulty)
if days_left == 1:
return max(job_difficulty[idx:])
max_difficulty = job_difficulty[idx]
days_left -= 1
stop = n - idx - days_left + 1
res = float("inf")
for i in range(1, stop):
max_difficulty = max(max_difficulty, job_difficulty[idx + i - 1])
other = self.helper(job_difficulty, days_left, idx + i)
res = min(res, other + max_difficulty)
return res
def minDifficulty(self, jobDifficulty, d):
"""
:type jobDifficulty: List[int]
:type d: int
:rtype: int
"""
if len(jobDifficulty) < d:
return -1
total_sum = sum(jobDifficulty)
if total_sum == 0:
return 0
return self.helper(jobDifficulty, d, 0)
if __name__ == "__main__":
obj = Solution()
print(obj.minDifficulty(jobDifficulty=[6, 5, 4, 3, 2, 1], d=2))
print(obj.minDifficulty(jobDifficulty=[9, 9, 9], d=4))
print(obj.minDifficulty(jobDifficulty=[1, 1, 1], d=3))
|