aboutsummaryrefslogtreecommitdiff
path: root/min_num_work_session.c
blob: 54f419059ba909ed17cd8844aaed9e9161e38b81 (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
52
53
54
55
56
57
58
// 1986. Minimum Number of Work Sessions to Finish the Tasks
#include "leetcode.h"

/*
 * there are 'n' tasks assigned to you. the task times are represented as an
 * integer array 'tasks' of length 'n' where the i'th task takes 'tasks[i]'
 * hours to finish. a work session is when you work for at most 'sessionTime'
 * consecutive hours, and then take a break. given 'tasks' and 'sessionTime',
 * return the minimum number of work sessions needed to finish all the tasks
 * following the conditions. the tests are generated such that 'sessionTime' is
 * greater or equal to the maximum element in 'tasks[i]'.
 */

int work(int *tasks, int tasksSize, int completed, int sessionTime,
         int time_remaining, int **dp) {
  int cnt, min = INT_MAX;
  if (completed == (1 << tasksSize) - 1)
    return 0;
  if (dp[completed][time_remaining] != -1)
    return dp[completed][time_remaining];
  for (int i = 0; i < tasksSize; i++) {
    if (!(completed & (1 << i))) {
      completed |= (1 << i);
      if (time_remaining - tasks[i] < 0)
        cnt = work(tasks, tasksSize, completed, sessionTime,
                   sessionTime - tasks[i], dp) +
              1;
      else
        cnt = work(tasks, tasksSize, completed, sessionTime,
                   time_remaining - tasks[i], dp);
      min = fmin(min, cnt);
      completed &= ~(1 << i);
    }
  }
  dp[completed][time_remaining] = min;
  return min;
}

int minSessions(int *tasks, int tasksSize, int sessionTime) {
  int **dp = (int **)malloc((1 << tasksSize) * sizeof(int *));
  for (int i = 0; i < (1 << tasksSize); i++) {
    dp[i] = (int *)malloc((sessionTime + 1) * sizeof(int));
    for (int j = 0; j <= sessionTime; j++)
      dp[i][j] = -1;
  }
  int ans = work(tasks, tasksSize, 0, sessionTime, 0, dp);
  for (int i = 0; i < (1 << tasksSize); i++)
    free(dp[i]);
  free(dp);
  return ans;
}

int main() {
  int t1[] = {1, 2, 3}, t2[] = {3, 1, 3, 1, 1}, t3[] = {1, 2, 3, 4, 5};
  printf("%d\n", minSessions(t1, ARRAY_SIZE(t1), 3));  // expect: 2
  printf("%d\n", minSessions(t2, ARRAY_SIZE(t2), 8));  // expect: 2
  printf("%d\n", minSessions(t3, ARRAY_SIZE(t3), 15)); // expect: 1
}