aboutsummaryrefslogtreecommitdiff
path: root/min_difficulty_schedule.c
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /min_difficulty_schedule.c
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'min_difficulty_schedule.c')
-rw-r--r--min_difficulty_schedule.c51
1 files changed, 51 insertions, 0 deletions
diff --git a/min_difficulty_schedule.c b/min_difficulty_schedule.c
new file mode 100644
index 0000000..c2296e5
--- /dev/null
+++ b/min_difficulty_schedule.c
@@ -0,0 +1,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
+}