aboutsummaryrefslogtreecommitdiff
path: root/min_difficulty_schedule.c
blob: c2296e527e67ff3bfc66eb78bcc6cedcf0baa636 (plain)
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
}