add 1733

fishercoder1534 · fishercoder1534 · commit 2e294a5a1ea5 · 2021-01-23T14:20:34.000-08: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                   
 |-----|----------------|---------------|--------|-------------|-------------
+|1733|[Minimum Number of People to Teach](https://leetcode.com/problems/minimum-number-of-people-to-teach/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1733.java) ||Medium|Array, Greedy|
 |1732|[Find the Highest Altitude](https://leetcode.com/problems/find-the-highest-altitude/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1732.java) ||Easy|Array|
 |1727|[Largest Submatrix With Rearrangements](https://leetcode.com/problems/largest-submatrix-with-rearrangements/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1727.java) ||Medium|Greedy, Sort|
 |1726|[Tuple with Same Product](https://leetcode.com/problems/tuple-with-same-product/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1726.java) ||Medium|Array|
diff --git a/src/main/java/com/fishercoder/solutions/_1733.java b/src/main/java/com/fishercoder/solutions/_1733.java
@@ -0,0 +1,46 @@
+package com.fishercoder.solutions;
+
+import java.util.*;
+
+public class _1733 {
+    public static class Solution1 {
+        public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
+            Map<Integer, Set<Integer>> langMap = new HashMap<>();
+            for (int i = 0; i < languages.length; i++) {
+                Set<Integer> set = new HashSet<>();
+                langMap.put(i + 1, set);
+                for (int lang : languages[i]) {
+                    set.add(lang);
+                }
+            }
+            boolean[] canCommunicate = new boolean[friendships.length];
+            for (int i = 1; i <= n; i++) {
+                for (int j = 0; j < friendships.length; j++) {
+                    int friend1 = friendships[j][0];
+                    int friend2 = friendships[j][1];
+                    if (langMap.get(friend1).contains(i) && langMap.get(friend2).contains(i)) {
+                        canCommunicate[j] = true;
+                    }
+                }
+            }
+            int minTeach = friendships.length;
+            for (int i = 1; i <= n; i++) {
+                Set<Integer> teach = new HashSet<>();
+                for (int j = 0; j < friendships.length; j++) {
+                    if (!canCommunicate[j]) {
+                        int friend1 = friendships[j][0];
+                        int friend2 = friendships[j][1];
+                        if (!langMap.get(friend1).contains(i)) {
+                            teach.add(friend1);
+                        }
+                        if (!langMap.get(friend2).contains(i)) {
+                            teach.add(friend2);
+                        }
+                    }
+                }
+                minTeach = Math.min(minTeach, teach.size());
+            }
+            return minTeach;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1733Test.java b/src/test/java/com/fishercoder/_1733Test.java
@@ -0,0 +1,35 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1733;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1733Test {
+    private static _1733.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1733.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        assertEquals(1, solution1.minimumTeachings(2, new int[][]{
+                {1}, {2}, {1, 2}
+        }, new int[][]{
+                {1, 2}, {1, 3}, {2, 3}
+        }));
+    }
+
+    @Test
+    public void test2() {
+        assertEquals(2, solution1.minimumTeachings(3, new int[][]{
+                {2}, {1, 3}, {1, 2}, {3}
+        }, new int[][]{
+                {1, 4}, {1, 2}, {3, 4}, {2, 3}
+        }));
+    }
+
+}
