add 2050

fishercoder1534 · fishercoder1534 · commit 7a7e79524665 · 2021-10-24T14:15:03.000-07:00
diff --git a/README.md b/README.md
@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ &#9733;
 
 |  #  |      Title     |   Solutions   | Video  | Difficulty  | Tag                  
 |-----|----------------|---------------|--------|-------------|-------------
+|2050|[Parallel Courses III](https://leetcode.com/problems/parallel-courses-iii/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2050.java) ||Hard||
 |2048|[Next Greater Numerically Balanced Number](https://leetcode.com/problems/next-greater-numerically-balanced-number/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2048.java) ||Medium||
 |2047|[Number of Valid Words in a Sentence](https://leetcode.com/problems/number-of-valid-words-in-a-sentence/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2047.java) ||Easy||
 |2044|[Count Number of Maximum Bitwise-OR Subsets](https://leetcode.com/problems/count-number-of-maximum-bitwise-or-subsets/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2044.java) ||Medium||
diff --git a/src/main/java/com/fishercoder/solutions/_2050.java b/src/main/java/com/fishercoder/solutions/_2050.java
@@ -0,0 +1,60 @@
+package com.fishercoder.solutions;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.Map;
+import java.util.Queue;
+import java.util.Set;
+
+public class _2050 {
+    public static class Solution1 {
+
+        /**
+         * My original solution, but results in TLE on LeetCode at 39/40 test cases...
+         */
+        public int minimumTime(int n, int[][] relations, int[] time) {
+            Map<Integer, Set<Integer>> prereqMap = new HashMap<>();
+            for (int[] rel : relations) {
+                int pre = rel[0];
+                int then = rel[1];
+                Set<Integer> list = prereqMap.getOrDefault(then, new HashSet<>());
+                list.add(pre);
+                prereqMap.put(then, list);
+            }
+            Queue<Integer> queue = new LinkedList<>();
+            Map<Integer, Integer> minMap = new HashMap<>();
+            for (int i = 0; i < n; i++) {
+                if (!prereqMap.containsKey(i + 1)) {
+                    minMap.put(i + 1, time[i]);
+                } else {
+                    queue.add(i + 1);
+                }
+            }
+            int minTime = 0;
+            while (!queue.isEmpty()) {
+                Integer curr = queue.poll();
+                int thisMinTime = Integer.MIN_VALUE;
+                Set<Integer> reqs = prereqMap.get(curr);
+                boolean valid = true;
+                for (int r : reqs) {
+                    if (!minMap.containsKey(r)) {
+                        queue.offer(curr);
+                        valid = false;
+                        break;
+                    } else {
+                        thisMinTime = Math.max(minMap.get(r), thisMinTime);
+                    }
+                }
+                if (valid) {
+                    minMap.put(curr, thisMinTime + time[curr - 1]);
+                }
+            }
+            for (int key : minMap.keySet()) {
+                minTime = Math.max(minTime, minMap.get(key));
+            }
+            return minTime;
+        }
+
+    }
+}
diff --git a/src/test/java/com/fishercoder/_2050Test.java b/src/test/java/com/fishercoder/_2050Test.java
@@ -0,0 +1,41 @@
+package com.fishercoder;
+
+import com.fishercoder.common.utils.CommonUtils;
+import com.fishercoder.solutions._2050;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _2050Test {
+    private static _2050.Solution1 solution1;
+    private static int[][] relation;
+    private static int[] time;
+    private static int n;
+    private static int expected;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _2050.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        n = 3;
+        relation = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[1,3],[2,3]");
+        time = new int[]{3, 2, 5};
+        expected = 8;
+        assertEquals(expected, solution1.minimumTime(n, relation, time));
+    }
+
+    @Test
+    public void test2() {
+        n = 5;
+        relation = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[1,5],[2,5],[3,5],[3,4],[4,5]");
+        time = new int[]{1, 2, 3, 4, 5};
+        expected = 12;
+        assertEquals(expected, solution1.minimumTime(n, relation, time));
+    }
+
+
+}
