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
|
// 1335. Minimum Difficulty of a Job Schedule
#include "leetcode.h"
/*
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.
*/
int minDifficulty(int *job_difficulty, int job_difficulty_size, int d) {
int maxValue = 10001, max_difficulty = 0;
if (job_difficulty_size < d)
return -1;
if (d == 1) {
for (int i = 0; i < job_difficulty_size; i++)
max_difficulty = fmax(max_difficulty, job_difficulty[i]);
return max_difficulty;
}
max_difficulty = 0;
int min_job_diff[job_difficulty_size + 1];
for (int i = 0; i < job_difficulty_size; i++)
min_job_diff[i] = maxValue;
min_job_diff[job_difficulty_size] = 0;
for (int day = 1; day <= d; ++day) {
for (int i = 0; i <= job_difficulty_size - day; i++) {
max_difficulty = 0, min_job_diff[i] = maxValue;
for (int j = i; j <= job_difficulty_size - day; j++) {
max_difficulty = fmax(max_difficulty, job_difficulty[j]);
min_job_diff[i] =
fmin(min_job_diff[i], max_difficulty + min_job_diff[j + 1]);
}
}
}
return min_job_diff[0];
}
int main() {
int jb1[] = {6, 5, 4, 3, 2, 1}, jb2[] = {9, 9, 9}, jb3[] = {1, 1, 1};
printf("%d\n", minDifficulty(jb1, ARRAY_SIZE(jb1), 2)); // expect: 7
printf("%d\n", minDifficulty(jb2, ARRAY_SIZE(jb2), 4)); // expect: -1
printf("%d\n", minDifficulty(jb3, ARRAY_SIZE(jb3), 3)); // expect: 3
}
|