LeetCode 621 Task Scheduler

[wupangyen]

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

[wupangyen]

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2 Output: 8 Explanation: A -> B -> idle -> A -> B -> idle -> A -> B There is at least 2 units of time between any two same tasks.

[wupangyen]

1. Greedy always process the task which has largest amount left
2. put task( count each char's frequency) in priority queue in descending order.
3. start to process tasks from the front of the queue. if amount left > 0 we put it into a coolDown hashmap
4. if there's task which cool down expired, put it into the queue and wait to be processed.
5. repeat step 3, 4 till there is no task left

[wupangyen]

public class Solution {

/*Greedy always process the task which has largest amount left

put task( count each char's frequency) in priority queue in descending order.

start to process tasks from the front of the queue. if amount left > 0 we put it into a coolDown hashmap

if there's task which cool down expired, put it into the queue and wait to be processed.

repeat step 3, 4 till there is no task left

*/ public int leastInterval(char[] tasks, int n) { // means there is no cool down time between each task if (n == 0) return tasks.length;

      // count the frequency of each char in the task
    // and put it into the hashmap
    Map<Character, Integer> taskToCount = new HashMap<>();
          //getOrDefault(key,defaultValue)
    //used to get the value mapped with specified key. if no value is mapped with the provided key then the default value is returned.
    //
    for (char c : tasks) {
        taskToCount.put(c, taskToCount.getOrDefault(c, 0) + 1);
    }
    // put the freq of char in priority in descending order
    Queue<Integer> queue = new PriorityQueue<>((i1, i2) -> i2 - i1);
        // ketSet()
// create a set out of the key elements contained in the hash map
    for (char c : taskToCount.keySet()) queue.offer(taskToCount.get(c));
       // cool down hashMap
    Map<Integer, Integer> coolDown = new HashMap<>();
    int currTime = 0;
    while (!queue.isEmpty() || !coolDown.isEmpty()) {
            //if there's task which cool down expired, put it into the queue and wait to be processed.
        if (coolDown.containsKey(currTime - n - 1)) {
            queue.offer(coolDown.remove(currTime - n - 1));
        }
        if (!queue.isEmpty()) {
         // poll return and removes element at front 

        // left is the remaining freq of each task
            int left = queue.poll() - 1;
        if (left != 0) coolDown.put(currTime, left);
        }
        currTime++;
    }

    return currTime;
}

}

[wupangyen]

above one is hard to understand I found another one is more simpler to understand

[wupangyen]

https://www.cnblogs.com/cnoodle/p/12778873.html

[wupangyen]

more readable solution

[wupangyen]

create a priority queue store the freq of each char the most frequent char will be at the top of the priority queue

create a variable call cycle length is n+ 1 this is the length of the cool down

now we start to pop char everytime we pop an char we put it in temporary list because we might need to add them back to pq

[wupangyen]

round robin, hashmap for freq of task

pq descending order for freq of char

n + 1 cycles, same task can only do only, so we use queue to help 中转 避免高频率的任务一直占着CPU every cycle, 执行完一轮之后再把queue里面的任务频率减1

如果还大于0，重新压入优先级队列继续下一轮轮询 只要pq优先级队列不空，我们就必须加（n+1）cycles到最后结果，即使中间有等待的时间(idle time)

如果最后一轮不满，则只需加实际执行的任务数目count。

[wupangyen]

class Solution { public int leastInterval(char[] tasks, int n) { //首先用pq建立一个最大堆，记录存每个字母的出现次数，出现次数最多的字母会在堆顶 HashMap<Character, Integer> counts = new HashMap<>(); for (char t : tasks) { counts.put(t, counts.getOrDefault(t, 0) + 1); } PriorityQueue queue = new PriorityQueue<>((a, b) -> b - a); queue.addAll(counts.values());

     int res = 0;
      //每个间隔的长度
     int cycle = n + 1;
     while (!queue.isEmpty()) {
         int worktime = 0;
         List<Integer> temp = new ArrayList<>();
         for (int i = 0; i < cycle; i++) {
             if (!queue.isEmpty()) {
                // 接着开始pop字符，每pop出一个字符的时候，将他加入一个临时的list，因为有可能还会再加回pq
                 temp.add(queue.poll());
                 worktime++;
             }
         }
         //执行完一轮之后再把queue里面的任务频率减1，如果还大于0，重新压入优先级队列继续下一轮轮询
         for (int count : temp) {
             if (--count > 0) {
                 queue.offer(count);
             }
         }

         //Conditional Operator ? :
        // booleanCondition ? executeThisPartIfBooleanConditionIsTrue : executeThisPartIfBooleanConditionIsFalse 
          // As long as pq is not empty, we have to add n + 1 cycles to res
        // it is possible that we didn't fully utilize the n + 1 cycles
        // meaning there could be CPU idle time
        // when pq is empty, meaning this is the last batch of tasks, we don't
        // have to wait full (n + 1) cycles if count < (n +1)

         //每次如果在cycle跑完之前，pq就遍历完了，则加入worktime，如果pq没有遍历完，则加入pq的size。
         res += !queue.isEmpty() ? cycle : worktime;
     }
     return res;
 }

}

[wupangyen]

answer for res += !queue.isEmpty() ? cycle : worktime; how to use it https://stackoverflow.com/questions/798545/what-is-the-java-operator-called-and-what-does-it-do

[wupangyen]

approach 3: more easier to understand

[wupangyen]

we need to arrange the characters in string such that each same character is K distance apart, distance is time between two similar task execution

add them to a priority queue and sort based on the highest frequency. and pick the task in each round of n with highest frequency

as you pick the task decrease the freq , and put them back after the round

[wupangyen]

public int leastInterval(char[] tasks, int n) { Map<Character, Integer> map = new HashMap<>(); for (int i = 0; i < tasks.length; i++) { map.put(tasks[i], map.getOrDefault(tasks[i], 0) + 1); // map key is TaskName, and value is number of times to be executed. } PriorityQueue<Map.Entry<Character, Integer>> q = new PriorityQueue<>( //frequency sort (a,b) -> a.getValue() != b.getValue() ? b.getValue() - a.getValue() : a.getKey() - b.getKey());

q.addAll(map.entrySet());

int count = 0;
while (!q.isEmpty()) {
    int k = n + 1;
    List<Map.Entry> tempList = new ArrayList<>();
    while (k > 0 && !q.isEmpty()) {
        Map.Entry<Character, Integer> top = q.poll(); // most frequency task
        top.setValue(top.getValue() - 1); // decrease frequency, meaning it got executed
        tempList.add(top); // collect task to add back to queue
        k--;
        count++; //successfully executed task
    }

    for (Map.Entry<Character, Integer> e : tempList) {
        if (e.getValue() > 0) q.add(e); // add valid tasks 
    }

    if (q.isEmpty()) break;
    count = count + k; // if k > 0, then it means we need to be idle
}
return count;

}

[wupangyen]

class Solution { public int leastInterval(char[] tasks, int n) { if (tasks == null || tasks.length == 0) return -1; //build map to sum the amount of each task HashMap<Character,Integer> map = new HashMap<>(); for (char ch:tasks){ map.put(ch,map.getOrDefault(ch,0)+1); }

    // build queue, sort from descending
    PriorityQueue<Map.Entry<Character,Integer>> queue = new PriorityQueue<>((a,b)->(b.getValue()-a.getValue()));
    queue.addAll(map.entrySet());

    int cnt = 0;
    // when queue is not empty, there are remaining tasks
    while (!queue.isEmpty()){
        // for each interval
        int interval = n+1;
        // list used to update queue
        List<Map.Entry<Character, Integer>> list = new ArrayList<>();

        // fill the intervals with the next high freq task
        while (interval > 0 && !queue.isEmpty()){
            Map.Entry<Character,Integer> entry = queue.poll();
            entry.setValue(entry.getValue()-1);
            list.add(entry);
            // interval shrinks
            interval --;
            // one slot is taken
            cnt ++;
        }

        // update the value in the map
        for (Map.Entry<Character,Integer> entry:list){
            // when there is left task
            if (entry.getValue() > 0)
                queue.offer(entry);
        }
        // job done
        if (queue.isEmpty())
            break;
        // if interval is > 0, then the machine can only be idle
        cnt += interval;
    }

    return cnt;

} }

[wupangyen]

the one with more comment

[wupangyen]

https://leetcode.com/problems/task-scheduler/discuss/104501/Java-PriorityQueue-solution-Similar-problem-Rearrange-string-K-distance-apart