aboutsummaryrefslogtreecommitdiff
path: root/min_num_work_session.c
diff options
context:
space:
mode:
Diffstat (limited to 'min_num_work_session.c')
-rw-r--r--min_num_work_session.c58
1 files changed, 58 insertions, 0 deletions
diff --git a/min_num_work_session.c b/min_num_work_session.c
new file mode 100644
index 0000000..54f4190
--- /dev/null
+++ b/min_num_work_session.c
@@ -0,0 +1,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
+}