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;
        }
    }

}

```
Todo
```

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)

Java

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;
    }
}

```
Todo
```

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)

621 - Task Scheduler

621. Task Scheduler

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

621. Task Scheduler

Level

Description

Solution

All Problems

All Solutions