621. 任务调度器

题目描述

输入字符数组 tasks，每个元素是一个大写字母，代表 CPU 要执行的一个任务，字母相同的任务属于同一种。另给一个非负整数 n 表示冷却时间。

CPU 每个时间单位要么执行一个任务，要么空闲待命。任务可以按任意顺序安排，但同一种任务的两次执行之间至少要隔开 n 个时间单位。

返回执行完全部任务所需的最少时间单位数，空闲的时间单位也计算在内。

示例 1

输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8

解释：一种安排是 A B 待命 A B 待命 A B，共 8 个单位。

示例 2

输入：tasks = ["A","C","A","B","D","B"], n = 1
输出：6

解释：例如 A B C D A B，不需要待命。

示例 3

输入：tasks = ["A","A","A","B","B","B"], n = 3
输出：10

解释：例如 A B 待命待命 A B 待命待命 A B，共 10 个单位。

数据范围

1 <= tasks.length <= 10^4
tasks[i] 是大写英文字母。
0 <= n <= 100

解题思路：大根堆 + 冷却队列模拟

贪心：每个时刻都执行“剩余次数最多且已经冷却好”的任务。剩余次数最多的任务最难安排，越早做越不容易在最后留下大段待命。用最大堆存可执行任务（按剩余次数），用一个队列存冷却中的任务以及它能再次执行的时刻。每过一个时间单位：堆非空就弹出堆顶执行，若还有剩余就进入冷却队列，解冻时刻 = 当前时刻 + n；堆为空说明只能待命，直接把时间跳到队首解冻的时刻。最后检查队首是否在这一刻解冻，解冻就放回堆中。

为什么正确

冷却队列按解冻时刻递增（因为入队时刻递增），堆里都是此刻可以执行的任务。

复杂度分析

时间 O(T log 26)，T 为任务总数（待命时直接跳时间，不逐格模拟）；空间 O(26)。

易错点

冷却 n 表示两次相同任务之间要隔 n 个单位，所以解冻时刻是 time + n，下一个可执行时刻是 time + n + 1：在本轮末尾解冻并放回堆，正好赶上下一轮。另外，公式解 (maxCnt−1)(n+1)+并列最大个数也可以，但要和任务总数取最大值。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        heap = [(-c, t) for t, c in collections.Counter(tasks).items()]
        heapq.heapify(heap)
        wait = collections.deque()
        time = 0
        while heap or wait:
            time += 1
            if heap:
                c, t = heapq.heappop(heap)
                if c + 1 < 0:
                    wait.append((c + 1, t, time + n))
            else:
                time = wait[0][2]
            if wait and wait[0][2] == time:
                c, t, _ = wait.popleft()
                heapq.heappush(heap, (c, t))
        return time

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] cnt = new int[26];
        for (char t : tasks) cnt[t - 'A']++;
        PriorityQueue<int[]> heap = new PriorityQueue<>((x, y) -> x[0] != y[0] ? y[0] - x[0] : x[1] - y[1]);
        for (int t = 0; t < 26; t++) if (cnt[t] > 0) heap.add(new int[]{cnt[t], t});
        Deque<int[]> wait = new ArrayDeque<>();
        int time = 0;
        while (!heap.isEmpty() || !wait.isEmpty()) {
            time++;
            if (!heap.isEmpty()) {
                int[] top = heap.poll();
                if (top[0] - 1 > 0) {
                    wait.addLast(new int[]{top[0] - 1, top[1], time + n});
                }
            } else {
                time = wait.peekFirst()[2];
            }
            if (!wait.isEmpty() && wait.peekFirst()[2] == time) {
                int[] w = wait.pollFirst();
                heap.add(new int[]{w[0], w[1]});
            }
        }
        return time;
    }
}

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        map<char, int> cnt;
        for (char t : tasks) cnt[t]++;
        priority_queue<pair<int, int>> heap;
        for (auto& [t, c] : cnt) heap.push({c, -t});
        deque<array<int, 3>> wait;
        int time = 0;
        while (!heap.empty() || !wait.empty()) {
            time++;
            if (!heap.empty()) {
                auto [c, t] = heap.top();
                heap.pop();
                if (c - 1 > 0) {
                    wait.push_back({c - 1, t, time + n});
                }
            } else {
                time = wait.front()[2];
            }
            if (!wait.empty() && wait.front()[2] == time) {
                auto w = wait.front();
                wait.pop_front();
                heap.push({w[0], w[1]});
            }
        }
        return time;
    }
};

type item struct{ c, t int }
type taskHeap []item

func (h taskHeap) Len() int { return len(h) }
func (h taskHeap) Less(i, j int) bool {
	if h[i].c != h[j].c {
		return h[i].c > h[j].c
	}
	return h[i].t < h[j].t
}
func (h taskHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *taskHeap) Push(x any)   { *h = append(*h, x.(item)) }
func (h *taskHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func leastInterval(tasks []byte, n int) int {
	cnt := [26]int{}
	for _, t := range tasks {
		cnt[t-'A']++
	}
	h := &taskHeap{}
	for t := 0; t < 26; t++ {
		if cnt[t] > 0 {
			heap.Push(h, item{cnt[t], t})
		}
	}
	wait := [][3]int{}
	time := 0
	for h.Len() > 0 || len(wait) > 0 {
		time++
		if h.Len() > 0 {
			top := heap.Pop(h).(item)
			if top.c-1 > 0 {
				wait = append(wait, [3]int{top.c - 1, top.t, time + n})
			}
		} else {
			time = wait[0][2]
		}
		if len(wait) > 0 && wait[0][2] == time {
			w := wait[0]
			wait = wait[1:]
			heap.Push(h, item{w[0], w[1]})
		}
	}
	return time
}

class MinHeap {
    constructor(less) { this.a = []; this.less = less; }
    get size() { return this.a.length; }
    push(x) {
        const a = this.a; a.push(x);
        for (let i = a.length - 1; i > 0;) {
            const p = (i - 1) >> 1;
            if (!this.less(a[i], a[p])) break;
            [a[i], a[p]] = [a[p], a[i]]; i = p;
        }
    }
    pop() {
        const a = this.a, top = a[0], last = a.pop();
        if (a.length) {
            a[0] = last;
            for (let i = 0; ;) {
                let m = i; const l = 2 * i + 1, r = l + 1;
                if (l < a.length && this.less(a[l], a[m])) m = l;
                if (r < a.length && this.less(a[r], a[m])) m = r;
                if (m === i) break;
                [a[i], a[m]] = [a[m], a[i]]; i = m;
            }
        }
        return top;
    }
}

var leastInterval = function(tasks, n) {
    const cnt = new Map();
    for (const t of tasks) cnt.set(t, (cnt.get(t) || 0) + 1);
    const heap = new MinHeap((x, y) => x[0] !== y[0] ? x[0] > y[0] : x[1] < y[1]);
    for (const [t, c] of cnt) heap.push([c, t]);
    const wait = [];
    let head = 0;
    let time = 0;
    while (heap.size || head < wait.length) {
        time++;
        if (heap.size) {
            const [c, t] = heap.pop();
            if (c - 1 > 0) {
                wait.push([c - 1, t, time + n]);
            }
        } else {
            time = wait[head][2];
        }
        if (head < wait.length && wait[head][2] === time) {
            const [c, t] = wait[head++];
            heap.push([c, t]);
        }
    }
    return time;
};

class MinHeap<T> {
    private a: T[] = [];
    constructor(private less: (x: T, y: T) => boolean) {}
    get size(): number { return this.a.length; }
    push(x: T): void {
        const a = this.a; a.push(x);
        for (let i = a.length - 1; i > 0;) {
            const p = (i - 1) >> 1;
            if (!this.less(a[i], a[p])) break;
            [a[i], a[p]] = [a[p], a[i]]; i = p;
        }
    }
    pop(): T {
        const a = this.a, top = a[0], last = a.pop()!;
        if (a.length) {
            a[0] = last;
            for (let i = 0; ;) {
                let m = i; const l = 2 * i + 1, r = l + 1;
                if (l < a.length && this.less(a[l], a[m])) m = l;
                if (r < a.length && this.less(a[r], a[m])) m = r;
                if (m === i) break;
                [a[i], a[m]] = [a[m], a[i]]; i = m;
            }
        }
        return top;
    }
}

function leastInterval(tasks: string[], n: number): number {
    const cnt = new Map<string, number>();
    for (const t of tasks) cnt.set(t, (cnt.get(t) || 0) + 1);
    const heap = new MinHeap<[number, string]>((x, y) => x[0] !== y[0] ? x[0] > y[0] : x[1] < y[1]);
    for (const [t, c] of cnt) heap.push([c, t]);
    const wait: [number, string, number][] = [];
    let head = 0;
    let time = 0;
    while (heap.size || head < wait.length) {
        time++;
        if (heap.size) {
            const [c, t] = heap.pop()!;
            if (c - 1 > 0) {
                wait.push([c - 1, t, time + n]);
            }
        } else {
            time = wait[head][2];
        }
        if (head < wait.length && wait[head][2] === time) {
            const [c, t] = wait[head++];
            heap.push([c, t]);
        }
    }
    return time;
}

载入编辑器，自己跑一遍 →

其他解法

堆模拟每一步贪心地选剩余最多的任务，能得到调度过程；公式法直接由最高频任务算出下界，并说明这个下界可以达到。

解法 2：桶思想公式时间 O(T)，空间 O(26)

设出现次数最多的任务出现 maxCount 次，共有 maxTasks 种任务达到这个次数。把时间轴切成 maxCount 个桶，前 maxCount − 1 个桶长 n + 1，最后一个桶只放这 maxTasks 个任务，总长 (maxCount − 1)·(n + 1) + maxTasks。其他任务按列填入空位即可满足冷却。空位不够时可以加宽桶，完全不需要待命，答案就是任务总数 T。两者取较大值。

只需一遍计数，代码最短。但只输出总时间，不给出具体执行顺序，并且正确性需要单独证明。

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        cnt = [0] * 26
        for t in tasks:
            cnt[ord(t) - 65] += 1
        maxCount = max(cnt)
        maxTasks = cnt.count(maxCount)
        return max(len(tasks), (maxCount - 1) * (n + 1) + maxTasks)

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] cnt = new int[26];
        for (char t : tasks) cnt[t - 'A']++;
        int maxCount = 0, maxTasks = 0;
        for (int c : cnt) maxCount = Math.max(maxCount, c);
        for (int c : cnt) if (c == maxCount) maxTasks++;
        return Math.max(tasks.length, (maxCount - 1) * (n + 1) + maxTasks);
    }
}

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        vector<int> cnt(26, 0);
        for (char t : tasks) cnt[t - 'A']++;
        int maxCount = *max_element(cnt.begin(), cnt.end());
        int maxTasks = count(cnt.begin(), cnt.end(), maxCount);
        return max((int)tasks.size(), (maxCount - 1) * (n + 1) + maxTasks);
    }
};

func leastInterval(tasks []byte, n int) int {
	cnt := [26]int{}
	for _, t := range tasks {
		cnt[t-'A']++
	}
	maxCount, maxTasks := 0, 0
	for _, c := range cnt {
		maxCount = max(maxCount, c)
	}
	for _, c := range cnt {
		if c == maxCount {
			maxTasks++
		}
	}
	return max(len(tasks), (maxCount-1)*(n+1)+maxTasks)
}

var leastInterval = function(tasks, n) {
    const cnt = new Array(26).fill(0);
    for (const t of tasks) cnt[t.charCodeAt(0) - 65]++;
    const maxCount = Math.max(...cnt);
    const maxTasks = cnt.filter(c => c === maxCount).length;
    return Math.max(tasks.length, (maxCount - 1) * (n + 1) + maxTasks);
};

function leastInterval(tasks: string[], n: number): number {
    const cnt = new Array(26).fill(0);
    for (const t of tasks) cnt[t.charCodeAt(0) - 65]++;
    const maxCount = Math.max(...cnt);
    const maxTasks = cnt.filter(c => c === maxCount).length;
    return Math.max(tasks.length, (maxCount - 1) * (n + 1) + maxTasks);
}

栈与堆专题的其他题目

查看栈与堆全部题目 →