Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

621. Task Scheduler #275

Open
Tcdian opened this issue Jul 28, 2020 · 1 comment
Open

621. Task Scheduler #275

Tcdian opened this issue Jul 28, 2020 · 1 comment
Labels

Comments

@Tcdian
Copy link
Owner

Tcdian commented Jul 28, 2020

621. Task Scheduler

给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行,并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务,或者在待命状态。

然而,两个 相同种类 的任务之间必须有长度为 n 的冷却时间,因此至少有连续 n 个单位时间内 CPU 在执行不同的任务,或者在待命状态。

你需要计算完成所有任务所需要的 最短时间

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.

Example 2

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: On this case any permutation of size 6 would work since n = 0.
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
And so on.

Example 3

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation: 
One possible solution is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

Note

  • 任务的总个数为 [1, 10000]
  • n 的取值范围为 [0, 100]
@Tcdian Tcdian added the Sort label Jul 28, 2020
@Tcdian
Copy link
Owner Author

Tcdian commented Jul 28, 2020

Solution

  • JavaScript Solution
/**
 * @param {character[]} tasks
 * @param {number} n
 * @return {number}
 */
var leastInterval = function(tasks, n) {
    const cache = new Array(26).fill(0);
    for (let i = 0; i < tasks.length; i++) {
        cache[tasks[i].codePointAt(0) - 65] += 1;
    }
    cache.sort((a, b) => b - a);
    const bucket = cache[0];
    let taskEqualBucket = 0;
    while(taskEqualBucket < 26 && cache[taskEqualBucket] === bucket) {
        taskEqualBucket++;
    }
    return Math.max((bucket - 1) * (n + 1) + taskEqualBucket, tasks.length);
};
  • TypeScript Solution
function leastInterval(tasks: string[], n: number): number {
    const cache: number[] = new Array(26).fill(0);
    for (let i = 0; i < tasks.length; i++) {
        cache[tasks[i].codePointAt(0) as number - 65] += 1;
    }
    cache.sort((a, b) => b - a);
    const bucket = cache[0];
    let taskEqualBucket = 0;
    while(taskEqualBucket < 26 && cache[taskEqualBucket] === bucket) {
        taskEqualBucket++;
    }
    return Math.max((bucket - 1) * (n + 1) + taskEqualBucket, tasks.length);
};

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant