Add solution #1494

JoshCrozier · JoshCrozier · commit f0bec56da029 · 2025-04-15T23:33:55.000-05:00
diff --git a/README.md b/README.md
@@ -1,4 +1,4 @@
-# 1,328 LeetCode solutions in JavaScript
+# 1,329 LeetCode solutions in JavaScript
 
 [https://leetcodejavascript.com](https://leetcodejavascript.com)
 
@@ -1142,6 +1142,7 @@
 1491|[Average Salary Excluding the Minimum and Maximum Salary](./solutions/1491-average-salary-excluding-the-minimum-and-maximum-salary.js)|Easy|
 1492|[The kth Factor of n](./solutions/1492-the-kth-factor-of-n.js)|Medium|
 1493|[Longest Subarray of 1's After Deleting One Element](./solutions/1493-longest-subarray-of-1s-after-deleting-one-element.js)|Medium|
+1494|[Parallel Courses II](./solutions/1494-parallel-courses-ii.js)|Hard|
 1496|[Path Crossing](./solutions/1496-path-crossing.js)|Easy|
 1502|[Can Make Arithmetic Progression From Sequence](./solutions/1502-can-make-arithmetic-progression-from-sequence.js)|Easy|
 1507|[Reformat Date](./solutions/1507-reformat-date.js)|Easy|
diff --git a/solutions/1494-parallel-courses-ii.js b/solutions/1494-parallel-courses-ii.js
@@ -0,0 +1,74 @@
+/**
+ * 1494. Parallel Courses II
+ * https://leetcode.com/problems/parallel-courses-ii/
+ * Difficulty: Hard
+ *
+ * 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] = [prevCoursei, nextCoursei], representing a
+ * prerequisite relationship between course prevCoursei and course nextCoursei: course prevCoursei
+ * has to be taken before course nextCoursei. Also, you are given the integer k.
+ *
+ * In one semester, you can take at most k courses 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.
+ */
+
+/**
+ * @param {number} n
+ * @param {number[][]} relations
+ * @param {number} k
+ * @return {number}
+ */
+var minNumberOfSemesters = function(n, relations, k) {
+  const prerequisites = new Array(n).fill(0);
+  for (const [prev, next] of relations) {
+    prerequisites[next - 1] |= 1 << (prev - 1);
+  }
+
+  const cache = new Array(1 << n).fill(-1);
+
+  return findMinSemesters(0);
+
+  function findMinSemesters(courses) {
+    if (courses === (1 << n) - 1) return 0;
+    if (cache[courses] !== -1) return cache[courses];
+
+    let available = 0;
+    for (let i = 0; i < n; i++) {
+      if (!(courses & (1 << i)) && (courses & prerequisites[i]) === prerequisites[i]) {
+        available |= 1 << i;
+      }
+    }
+
+    let minSemesters = n + 1;
+    const combinations = function(pos, count, selected) {
+      if (count === 0 || pos === n) {
+        if (selected) {
+          minSemesters = Math.min(
+            minSemesters,
+            1 + findMinSemesters(courses | selected)
+          );
+        }
+        return;
+      }
+      if (!(available & (1 << pos))) return combinations(pos + 1, count, selected);
+      combinations(pos + 1, count - 1, selected | (1 << pos));
+      combinations(pos + 1, count, selected);
+    };
+
+    combinations(0, Math.min(k, bitCount(available)), 0);
+    cache[courses] = minSemesters;
+    return minSemesters;
+  }
+
+  function bitCount(num) {
+    let count = 0;
+    while (num) {
+      count += num & 1;
+      num >>= 1;
+    }
+    return count;
+  }
+};
