add 621

fishercoder1534 · fishercoder1534 · commit 20fff9de559e · 2017-06-20T14:14:43.000+09:00
diff --git a/README.md b/README.md
@@ -23,6 +23,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |625|[Minimum Factorization](https://leetcode.com/problems/minimum-factorization/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_625.java) | O(?) |O(?) | Medium | 
 |624|[Maximum Distance in Arrays](https://leetcode.com/problems/maximum-distance-in-arrays/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_624.java) | O(nlogn) |O(1) | Easy | Sort, Array
 |623|[Add One Row to Tree](https://leetcode.com/problems/add-one-row-to-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_623.java) | O(n) |O(h) | Medium | Tree
+|621|[Task Scheduler](https://leetcode.com/problems/task-scheduler/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_621.java) | O(n) |O(26) | Medium | Greedy, Queue
 |617|[Merge Two Binary Trees](https://leetcode.com/problems/merge-two-binary-trees/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_617.java) | O(n) |O(h) | Easy | Tree, Recursion
 |616|[Add Bold Tag in String](https://leetcode.com/problems/add-bold-tag-in-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_616.java) | O(n*k) (n is length of string, k is size of dict) |O(n) | Medium | String
 |611|[Valid Triangle Number](https://leetcode.com/problems/valid-triangle-number/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_611.java) | O(n^2logn) |O(logn) | Medium | Binary Search
diff --git a/src/main/java/com/fishercoder/solutions/_621.java b/src/main/java/com/fishercoder/solutions/_621.java
@@ -0,0 +1,71 @@
+package com.fishercoder.solutions;
+
+import java.util.*;
+
+/**
+ * 621. Task Scheduler
+ *
+ * Given a char array representing tasks CPU need to do.
+ * It contains capital letters A to Z where different letters represent different tasks.
+ * Tasks could be done without original order.
+ * Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.
+ * However, there is a non-negative cooling interval n that means between two same tasks,
+ * there must be at least n intervals that CPU are doing different tasks or just be idle.
+ * You need to return the least number of intervals the CPU will take to finish all the given tasks.
+
+ Example 1:
+ Input: tasks = ['A','A','A','B','B','B'], n = 2
+ Output: 8
+ Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
+
+ Note:
+ The number of tasks is in the range [1, 10000].
+ The integer n is in the range [0, 100].
+ */
+public class _621 {
+
+    /**Could be simplified just using an array to record the frequencies of each letter, like this one:
+     * https://leetcode.com/articles/task-scheduler/#approach-2-using-priority-queue-accepted*/
+    public int leastInterval(char[] tasks, int n) {
+        Map<Character, Integer> map = new HashMap<>();
+        for (char c : tasks) {
+            map.put(c, map.getOrDefault(c, 0) + 1);
+        }
+        PriorityQueue<Task> maxHeap = new PriorityQueue<>((a, b) -> b.total - a.total);
+        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
+            maxHeap.offer(new Task(entry.getValue(), entry.getKey()));
+        }
+        int times = 0;
+        while (!maxHeap.isEmpty()) {
+            int i = 0;
+            List<Task> temp = new ArrayList<>();
+            while (i <= n) {
+                if (!maxHeap.isEmpty()) {
+                    if (maxHeap.peek().total > 1) {
+                        Task curr = maxHeap.poll();
+                        temp.add(new Task(curr.total-1, curr.character));
+                    } else {
+                        maxHeap.poll();
+                    }
+                }
+                times++;
+                if (maxHeap.isEmpty() && temp.size() == 0) break;
+                i++;
+            }
+            for (Task task : temp) {
+                maxHeap.offer(task);
+            }
+        }
+        return times;
+    }
+
+    class Task {
+        int total;
+        char character;
+        public Task(int total, char character) {
+            this.total = total;
+            this.character = character;
+        }
+    }
+
+}
diff --git a/src/test/java/com/fishercoder/_621Test.java b/src/test/java/com/fishercoder/_621Test.java
@@ -0,0 +1,26 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._621;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Created by stevesun on 6/19/17.
+ */
+public class _621Test {
+    private static _621 test;
+    private static char[] tasks;
+
+    @BeforeClass
+    public static void setup(){
+        test = new _621();
+    }
+
+    @Test
+    public void test1(){
+        tasks = new char[]{'A','A','A','B','B','B'};
+        assertEquals(8, test.leastInterval(tasks, 2));
+    }
+}
