Task Scheduler

Info

🔗 Leetcode-621. Task Scheduler

You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there's a constraint: identical tasks must be separated by at least n intervals due to cooling time.

Return the minimum number of intervals required to complete all tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2

Output: 8

Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.

After completing task A, you must wait two cycles before doing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th cycle, you can do A again as 2 intervals have passed.

Example 2:

Input: tasks = ["A","C","A","B","D","B"], n = 1

Output: 6

Explanation: A possible sequence is: A -> B -> C -> D -> A -> B.

With a cooling interval of 1, you can repeat a task after just one other task.

Example 3:

Input: tasks = ["A","A","A", "B","B","B"], n = 3

Output: 10

Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B.

There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.

Constraints:

• 1 <= tasks.length <= 104
• tasks[i] is an uppercase English letter.
• 0 <= n <= 100

Thoughts

Precondition:

• Be careful that the condition 0 <= n <= 100

First thought when taking a look at the problem:

• ❌ Can dp work? No: we have to iterate the whole arrays to get information of the size of char-category and the count of each char. Then we are able to do next step. So it at least has Oⁿ time-complexity.
• 🤔 Greedy? May work, put it aside first.
• 🤔 Sldie-Window? Thinking of a n-size sliding window as steps goes on. May work. -> Similarly, Stack or Queue?
• 🤔 Math? Probably work.
• ✅ Simulation: Create three working buckets to express three different status, and simulate the whole progress.

Solution

Simulation

Precondition: Iterates the arrays to count the numbers of each char. This is because we are unable to make a dynamic plan in runtime, owing to the reason that any new added char can easily overthrow previous plan.

Scene Converting

Try to convert this question into real-world problem. Take the example of Single-Core Chip.

Scene: One single-core chip can handle only one task each time of its circle, and it is not allowed to handle task of same kind in at least n periods. So now, we are trying to get the shortest time to execute a task array.

Thinking the progress as a whole and converting to thinking like a machine, there will be three different status for this problem:

• Holders-Pool(Ready to be selected): Chars has remaining tasks, and which had been selected before more than n-intervals or are not selected at the beginning.
• Workers-Pool(Running, not ready to be selected): Chars which were selected and handled before intervals of less than or equal to n.
• Done-Pool: Chars that already have no remaining candidate. (Actually, this status can be ignored in this situation.)

So, we can simulate the solution in process below:

• Check the Ready-Pool, if there is any remaining candidiate of any char.
  • No, we’ve found the shortest executing time. End
  • Yes, choose a right candidate to make our program definitely run in shortest time.

How to make a right move each time?

We make sure that each time we select the char that has most remaining count in the Ready-Pool. It’s easy to think of that in the first time. But it may tak some complicated efforts to be proved, which is illustrated later.

Code

class Solution {
    public int leastInterval(char[] tasks, int n) {
        // 0 <= n <= 100
      	// Optimization: reduce size from 26 to actual size(collecting char which has remaining count)
        int index = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (char c : tasks) {
            if (map.get(c) == null) {
                map.put(c, index++);
            }
        }
      	// Initial holders and workers
        int[] holders = new int[index];
        int[] workers = new int[index];
        for (char c : tasks) {
            holders[map.get(c)]++;
        }
        int step = 0;
        while(true) {
            int candidate = -1;
            int avaliableMaxCount = 0;
            boolean flag = true;
          	// Try to find the holder that holds most tasks
            for (int i = 0; i < holders.length; i++) {
                if (holders[i] > 0) {
                    flag = false;
                }
                if (holders[i] > avaliableMaxCount && (workers[i] == 0 || workers[i] > n)) {
                    candidate = i;
                    avaliableMaxCount = holders[i];
                    workers[i] = 0;
                }
            }
          	// Judegment: If no remaining holder, then quit
            if (flag) {
                break;
            }
          	// Records that worker-tasks has been handled for one day again
            for (int i = 0; i < workers.length; i++) {
                if (workers[i] > 0) {
                    workers[i]++;
                }
            }
            if (candidate >= 0) {
                holders[candidate]--;
                workers[candidate]++;
            }
          	// Simulate successfully handled one task
            step++;
        }
        return step;
    }
}

Complexity

Assume:

• $\text{tasks}$ : total task number
• $\mathrm{\Sigma }$: kinds of task

Time Complexity: $O(|tasks|\ast |\mathrm{\Sigma }|)$​

Space Complexty: $O(|\mathrm{\Sigma }|)$

Result-1

Math & Intuition (Copy)

Core: Idea Of Buckets.

Take N+1 buckets to hold task (as a kind of period), and try to fill buckets with task each round. Dividided the total periods/rounds: Start of one period must begin with the kind which has most tasks.

We should taking account of sitautions below($\mathrm{\Sigma }$: kinds of task):

1. Cost of buckets each round equal to N + 1 (Only small kinds of task)

$$|\mathrm{\Sigma }|\le N+1$$

So the cost of each period will strictly equal to N+1, as there may be some intervals in some period.

In this situation, the result can be calculated in O(1) time-complexity with intuition math formula.
(Assume $M$ as the numbers of the most kind task, and $\mathrm{\Delta }$ as the tasks that last bucket holds)

$$C(N)=\underset{\text{Cost of first M - 1 rounds}}{\underbrace{(M-1)\ast (N+1)}}+\underset{\text{Cost of last round}}{\underbrace{|\mathrm{\Delta }|}}$$

How to calculate the numbers of last buckets?

In this situation, tasks which are hold on the last round definitely have the same total number with the most-common kind task.(Otherwise it can be filled in buckets in previous round.)

$$\mathrm{\Delta }=\sum (\text{kinds of task which hold the same most numbers})$$

2. Sometimes the cost of some buckets can go beyond with N+1 (Too many kinds of task)

$$|\mathrm{\Sigma }|>N+1$$

Look at the fisrt time, it seems that we could not use the formula any more and it’s complicated to include special situation.

But what if we allow the bucket to grow properly at some point, which means that the cost of each period is not strictly equalled. Which also measn that there will be no intervals.(Have to think this point through, better with graph).In this situation, the result is the numbers of all tasks.

$$C(N)=\sum _{i=1}^{n}task(i)$$

And in this situation the result definitely no less than the first. So we finally reach the answer

$$C(N)=Math.max((\underset{\text{Cost of first M - 1 buckets}}{\underbrace{(M-1)\ast (N+1)}}+\underset{\text{Cost of last bucket}}{\underbrace{|\mathrm{\Delta }|}}),\sum _{i=1}^{n}task(i))$$

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] buckets = new int[26];
				// Good way to hash char and its count
        for(int i = 0; i < tasks.length; i++){
            buckets[tasks[i] - 'A']++;
        }
      	// Sort the array to get the numbers of most-common kinds
        Arrays.sort(buckets);
        int maxTimes = buckets[25];
        int maxCount = 1;
      	// Get the numbers of most-common kinds
        for(int i = 25; i >= 1; i--){
            if(buckets[i] == buckets[i - 1])
                maxCount++;
            else
                break;
        }
      	// Formula
        int res = (maxTimes - 1) * (n + 1) + maxCount;
        return Math.max(res, tasks.length);
    }
}

Result

Assume:

• $\text{tasks}$ : total task number
• $\mathrm{\Sigma }$: kinds of task

Time Complexity: $O(\mathrm{\Sigma }\ast lg(\mathrm{\Sigma }))$ (Determined by sort algo)​

Space Complexty: $O(lg(\mathrm{\Sigma }))$ (Determined by sort algo)