commit dac10095fd54f29edb2e262a408a515de725a0e8
parent 387b3ecf24e20ffaaafcf111654b04e14ffd7704
Author: Jack Sangdahl <jack@pngu.org>
Date: Mon, 29 Dec 2025 20:17:35 -0700
1494. parallel courses 2
Diffstat:
2 files changed, 117 insertions(+), 0 deletions(-)
diff --git a/parallel_courses2.c b/parallel_courses2.c
@@ -0,0 +1,67 @@
+// 1494. Parallel Courses II
+#include "leetcode.h"
+
+/*
+ * you are given an integer 'n' which indicates that there are 'n' courses
+ * labeled from 1 to 'n'. you are also given an array 'relations' where
+ * 'relations[i] = [prev_course[i], next_course[i]]', representing a
+ * prerequisite relationship between course 'prev_course' and course
+ * 'next_course': course 'prev_course' has to be taken before 'next_course'.
+ * also, you are given integer 'k'. in one semester, you can take most 'k'
+ * course as long as you have taken all the prerequisites in the previous
+ * semesters for the courses you are taking. return the minimum number of
+ * semesters needed to take all courses. the testcases will be generated such
+ * that it is possible to take every course.
+ */
+
+int minNumberOfSemesters(int n, int **relations, int relationsSize,
+ int *relationsColSize, int k) {
+ int *dp = (int *)malloc((1 << n) * sizeof(int));
+ int *prereq = (int *)calloc(1 << n, sizeof(int));
+ int *pre_course = (int *)malloc(n);
+ for (int i = 0; i < (1 << n); i++)
+ dp[i] = INT_MAX / 2;
+ for (int i = 0; i < relationsSize; i++) {
+ int u = relations[i][0] - 1;
+ int v = relations[i][1] - 1;
+ pre_course[v] |= (1 << u);
+ }
+ for (int i = 0; i < (1 << n); i++) {
+ for (int j = 0; j < n; j++)
+ if ((i >> j) & 1)
+ prereq[i] |= pre_course[j];
+ if (!prereq[i] && __builtin_popcount(i) <= k)
+ dp[i] = 1;
+ }
+ dp[0] = 0;
+ for (int i = 0; i < (1 << n); i++) {
+ int x = __builtin_popcount(i);
+ for (int j = i; j > 0; j = ((j - 1) & j)) {
+ int y = __builtin_popcount(j);
+ if (x - y > k)
+ continue;
+ if ((prereq[i] & j) == prereq[i])
+ dp[i] = fmin(dp[i], dp[j] + 1);
+ }
+ }
+ int ans = (dp[(1 << n) - 1] == INT_MAX / 2) ? -1 : dp[(1 << n) - 1];
+ free(dp);
+ free(prereq);
+ free(pre_course);
+ return ans;
+}
+
+int main() {
+ int r1i[3][2] = {{2, 1}, {3, 1}, {1, 4}};
+ int r2i[4][2] = {{2, 1}, {3, 1}, {4, 1}, {1, 5}};
+ struct two_d_arr *r1 =
+ two_d_arr_init(ARRAY_SIZE(r1i), ARRAY_SIZE(r1i[0]), r1i);
+ struct two_d_arr *r2 =
+ two_d_arr_init(ARRAY_SIZE(r2i), ARRAY_SIZE(r2i[0]), r2i);
+ printf("%d\n", minNumberOfSemesters(4, r1->arr, r1->row_size, r1->col_size,
+ 2)); // expect: 3
+ printf("%d\n", minNumberOfSemesters(5, r2->arr, r2->row_size, r2->col_size,
+ 2)); // expect: 4
+ two_d_arr_free(r1);
+ two_d_arr_free(r2);
+}
diff --git a/parallel_courses2.py b/parallel_courses2.py
@@ -0,0 +1,50 @@
+# 1494. Parallel Courses II
+from itertools import permutations
+
+"""
+you are given an integer 'n' which indicates that there are 'n' courses
+labeled from 1 to 'n'. you are also given an array 'relations' where
+'relations[i] = [prev_course[i], next_course[i]]', representing a
+prerequisite relationship between course 'prev_course' and course
+'next_course': course 'prev_course' has to be taken before 'next_course'.
+also, you are given integer 'k'. in one semester, you can take most 'k'
+course as long as you have taken all the prerequisites in the previous
+semesters for the courses you are taking. return the minimum number of
+semesters needed to take all courses. the testcases will be generated such
+that it is possible to take every course.
+"""
+
+
+class Solution(object):
+ def minNumberOfSemesters(self, n, relations, k):
+ """
+ :type n: int
+ :type relations: List[List[int]]
+ :type k: int
+ :rtype: int
+ """
+ dp = [[(100, 0, 0)] * n for _ in range(1 << n)]
+ prereq = [0] * n
+ for i, j in relations:
+ prereq[j - 1] ^= 1 << (i - 1)
+ for i in range(n):
+ if prereq[i] == 0:
+ dp[1 << i][i] = (1, 1, 1 << i)
+ for i in range(1 << n):
+ nz_bit = [len(bin(i)) - j - 1 for j, l in enumerate(bin(i)) if l == "1"]
+ for j, l in permutations(nz_bit, 2):
+ if prereq[l] & i == prereq[l]:
+ candid, bits, mask = dp[i ^ (1 << l)][j]
+ if prereq[l] & mask == 0 and bits < k:
+ dp[i][l] = min(dp[i][l], (candid, bits + 1, mask + (1 << l)))
+ else:
+ dp[i][l] = min(dp[i][l], (candid + 1, 1, 1 << l))
+ return min([i for i, j, k in dp[-1]])
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minNumberOfSemesters(n=4, relations=[[2, 1], [3, 1], [1, 4]], k=2))
+ print(
+ obj.minNumberOfSemesters(n=5, relations=[[2, 1], [3, 1], [4, 1], [1, 5]], k=2)
+ )
