Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/621.html
621. Task Scheduler
Level
Medium
Description
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:
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].
Solution
Use priority queue. Each element in the priority queue is an object that contains a task and the count of the task, where the task with the maximum count is polled fist.
Loop over tasks and count the number of each task, and for each task, create an object of the task and its count and offer the object into the priority queue.
Since the cooling interval n is given, doing n + 1 different tasks each round won’t have idle time. Therefore, each round select at most n + 1 objects of different tasks from the priority queue, update their counts and add the number of intervals to the total number of intervals. If there are remaining tasks, then add idle intervals if necessary. Then offer the updated objects to the priority queue.
Finally, return the total number of intervals.
-
public class Task_Scheduler { // ref https://leetcode.com/articles/task-scheduler/ public class Solution_heap { public int leastInterval(char[] tasks, int n) { int[] map = new int[26]; for (char c : tasks) map[c - 'A']++; PriorityQueue<Integer> queue = new PriorityQueue<>(26, Collections.reverseOrder()); for (int f : map) { if (f > 0) queue.add(f); } // picking up the largest task from the queuequeue for current execution int time = 0; while (!queue.isEmpty()) { int i = 0; List<Integer> temp = new ArrayList<>(); while (i <= n) { if (!queue.isEmpty()) { if (queue.peek() > 1) temp.add(queue.poll() - 1); else queue.poll(); } time++; if (queue.isEmpty() && temp.size() == 0) break; i++; } for (int l : temp) queue.add(l); } return time; } } public class Solution { public int leastInterval(char[] tasks, int n) { int[] map = new int[26]; for (char c: tasks) { map[c - 'A']++; } Arrays.sort(map); int time = 0; while (map[25] > 0) { int i = 0; while (i <= n) { if (map[25] == 0) break; if (i < 26 && map[25 - i] > 0) map[25 - i]--; time++; i++; } Arrays.sort(map); } return time; } } } ############ class Solution { public int leastInterval(char[] tasks, int n) { int[] cnt = new int[26]; int x = 0; for (char c : tasks) { c -= 'A'; ++cnt[c]; x = Math.max(x, cnt[c]); } int s = 0; for (int v : cnt) { if (v == x) { ++s; } } return Math.max(tasks.length, (x - 1) * (n + 1) + s); } } -
class Solution: def leastInterval(self, tasks: List[str], n: int) -> int: cnt = Counter(tasks) x = max(cnt.values()) s = sum(v == x for v in cnt.values()) return max(len(tasks), (x - 1) * (n + 1) + s) ############ class Solution(object): # O(nlogn) greedy to place most popular and distinct tasks first # Actually, I don't think this is greedy # We always place different tasks in a cycle which will minimize steps # If not different tasks can be placed in a cycle, place an `idle`. def _leastInterval(self, tasks, n): """ :type tasks: List[str] :type n: int :rtype: int """ n += 1 ans = 0 d = collections.Counter(tasks) heap = [-c for c in d.values()] heapq.heapify(heap) while heap: stack = [] cnt = 0 for _ in range(n): if heap: c = heapq.heappop(heap) cnt += 1 if c < -1: stack.append(c + 1) for item in stack: heapq.heappush(heap, item) ans += heap and n or cnt # == if heap then n else cnt return ans # O(n) # of the most frequent tasks, say longest, will determine the legnth # to void counting idle intervals, we count (longest - 1) * (n + 1) # then count how many will in the last cycle which means finding ties # if counted number is less than # of tasks which means # less frequent tasks can be always placed in such cycle # and it won't cause any conflicts with requirement since even most frequent can be settle # finally, return max(# of task, total counted number) def leastInterval(self, tasks, n): d = collections.Counter(tasks) counts = d.values() longest = max(counts) ans = (longest - 1) * (n + 1) for count in counts: ans += count == longest and 1 or 0 return max(len(tasks), ans) -
class Solution { public: int leastInterval(vector<char>& tasks, int n) { vector<int> cnt(26); int x = 0; for (char c : tasks) { c -= 'A'; ++cnt[c]; x = max(x, cnt[c]); } int s = 0; for (int v : cnt) { s += v == x; } return max((int) tasks.size(), (x - 1) * (n + 1) + s); } }; -
func leastInterval(tasks []byte, n int) int { cnt := make([]int, 26) x := 0 for _, c := range tasks { c -= 'A' cnt[c]++ x = max(x, cnt[c]) } s := 0 for _, v := range cnt { if v == x { s++ } } return max(len(tasks), (x-1)*(n+1)+s) } func max(a, b int) int { if a > b { return a } return b } -
public class Solution { public int LeastInterval(char[] tasks, int n) { int[] cnt = new int[26]; int x = 0; foreach (char c in tasks) { cnt[c - 'A']++; x = Math.Max(x, cnt[c - 'A']); } int s = 0; foreach (int v in cnt) { s = v == x ? s + 1 : s; } return Math.Max(tasks.Length, (x - 1) * (n + 1) + s); } }
-
class Solution { public int leastInterval(char[] tasks, int n) { Map<Character, Integer> map = new HashMap<Character, Integer>(); for (char task : tasks) { int count = map.getOrDefault(task, 0); count++; map.put(task, count); } PriorityQueue<TaskCount> priorityQueue = new PriorityQueue<TaskCount>(); Set<Character> set = map.keySet(); for (char task : set) { int count = map.getOrDefault(task, 0); TaskCount taskCount = new TaskCount(task, count); priorityQueue.offer(taskCount); } int intervals = 0; while (!priorityQueue.isEmpty()) { int size = priorityQueue.size(); int curTasks = Math.min(size, n + 1); List<TaskCount> curList = new ArrayList<TaskCount>(); for (int i = 0; i < curTasks; i++) { TaskCount taskCount = priorityQueue.poll(); taskCount.count--; if (taskCount.count > 0) curList.add(taskCount); } intervals += curList.isEmpty() ? curTasks : n + 1; for (TaskCount taskCount : curList) priorityQueue.offer(taskCount); } return intervals; } } class TaskCount implements Comparable<TaskCount> { public char task; public int count; public TaskCount() { } public TaskCount(char task, int count) { this.task = task; this.count = count; } public int compareTo(TaskCount taskCount2) { if (this.count != taskCount2.count) return taskCount2.count - this.count; else return this.task - taskCount2.task; } } ############ class Solution { public int leastInterval(char[] tasks, int n) { int[] cnt = new int[26]; int x = 0; for (char c : tasks) { c -= 'A'; ++cnt[c]; x = Math.max(x, cnt[c]); } int s = 0; for (int v : cnt) { if (v == x) { ++s; } } return Math.max(tasks.length, (x - 1) * (n + 1) + s); } } -
class Solution: def leastInterval(self, tasks: List[str], n: int) -> int: cnt = Counter(tasks) x = max(cnt.values()) s = sum(v == x for v in cnt.values()) return max(len(tasks), (x - 1) * (n + 1) + s) ############ class Solution(object): # O(nlogn) greedy to place most popular and distinct tasks first # Actually, I don't think this is greedy # We always place different tasks in a cycle which will minimize steps # If not different tasks can be placed in a cycle, place an `idle`. def _leastInterval(self, tasks, n): """ :type tasks: List[str] :type n: int :rtype: int """ n += 1 ans = 0 d = collections.Counter(tasks) heap = [-c for c in d.values()] heapq.heapify(heap) while heap: stack = [] cnt = 0 for _ in range(n): if heap: c = heapq.heappop(heap) cnt += 1 if c < -1: stack.append(c + 1) for item in stack: heapq.heappush(heap, item) ans += heap and n or cnt # == if heap then n else cnt return ans # O(n) # of the most frequent tasks, say longest, will determine the legnth # to void counting idle intervals, we count (longest - 1) * (n + 1) # then count how many will in the last cycle which means finding ties # if counted number is less than # of tasks which means # less frequent tasks can be always placed in such cycle # and it won't cause any conflicts with requirement since even most frequent can be settle # finally, return max(# of task, total counted number) def leastInterval(self, tasks, n): d = collections.Counter(tasks) counts = d.values() longest = max(counts) ans = (longest - 1) * (n + 1) for count in counts: ans += count == longest and 1 or 0 return max(len(tasks), ans) -
class Solution { public: int leastInterval(vector<char>& tasks, int n) { vector<int> cnt(26); int x = 0; for (char c : tasks) { c -= 'A'; ++cnt[c]; x = max(x, cnt[c]); } int s = 0; for (int v : cnt) { s += v == x; } return max((int) tasks.size(), (x - 1) * (n + 1) + s); } }; -
func leastInterval(tasks []byte, n int) int { cnt := make([]int, 26) x := 0 for _, c := range tasks { c -= 'A' cnt[c]++ x = max(x, cnt[c]) } s := 0 for _, v := range cnt { if v == x { s++ } } return max(len(tasks), (x-1)*(n+1)+s) } func max(a, b int) int { if a > b { return a } return b } -
public class Solution { public int LeastInterval(char[] tasks, int n) { int[] cnt = new int[26]; int x = 0; foreach (char c in tasks) { cnt[c - 'A']++; x = Math.Max(x, cnt[c - 'A']); } int s = 0; foreach (int v in cnt) { s = v == x ? s + 1 : s; } return Math.Max(tasks.Length, (x - 1) * (n + 1) + s); } }