LeetCode 621. 任务调度器

Categories:

题目描述
思路分析
1. 解法一：贪心公式（推荐）
相似题目

题目描述

✅ 621. 任务调度器

思路分析

解法一：贪心公式（推荐）

核心思路：

统计每个任务的出现次数，设最大频次为 maxCount。

将这些任务按 maxCount - 1 个间隔分成 maxCount - 1 个桶，每个桶长度至少 n + 1。

若有多个任务达到最大频次，最后一个桶需要补上 numMax 个。

结果为 max(total, (maxCount - 1) * (n + 1) + numMax)。

复杂度分析：

时间复杂度：O(n)，其中 n 表示任务数量。

空间复杂度：O(1)，字母表大小固定。

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] cnt = new int[26];
        for (char c : tasks) {
            cnt[c - 'A']++;
        }

        int maxCount = 0;
        for (int v : cnt) {
            maxCount = Math.max(maxCount, v);
        }

        int numMax = 0;
        for (int v : cnt) {
            if (v == maxCount) {
                numMax++;
            }
        }

        int part = (maxCount - 1) * (n + 1) + numMax;
        return Math.max(tasks.length, part);
    }
}

func leastInterval(tasks []byte, n int) int {
	cnt := make([]int, 26)
	for _, c := range tasks {
		cnt[c-'A']++
	}

	maxCount := 0
	for _, v := range cnt {
		if v > maxCount {
			maxCount = v
		}
	}

	numMax := 0
	for _, v := range cnt {
		if v == maxCount {
			numMax++
		}
	}

	part := (maxCount-1)*(n+1) + numMax
	if part > len(tasks) {
		return part
	}
	return len(tasks)
}

相似题目

题目	难度	考察点
621. 任务调度器	中等	贪心、计数
767. 重构字符串	中等	贪心、堆
358. K 距离间隔重排字符串	困难	贪心、堆
1054. 距离相等的条形码	中等	贪心、计数
1405. 最长快乐字符串	中等	贪心、堆
239. 滑动窗口最大值	困难	队列/堆

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/36140983