From d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa Mon Sep 17 00:00:00 2001 From: jack <0x6A73@pm.me> Date: Fri, 14 Jun 2024 13:13:15 -0600 Subject: initial --- min_difficulty_schedule.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 51 insertions(+) create mode 100644 min_difficulty_schedule.c (limited to 'min_difficulty_schedule.c') 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 +} -- cgit v1.2.3