vvrf / DSA.log

问题拆解

CPU 执行任务，每个时间单位做一个任务或待命，相同种类的任务之间必须间隔至少 n 个时间单位，求完成所有任务的最短时间。

真正卡脖子的是出现次数最多的那种任务：设它出现 maxCount 次，相邻两次之间必须隔 n 个单位，所以它自己就撑起了一条最短的时间轴。与其模拟每一步选哪个任务，不如直接以它为骨架搭框架：把 maxCount 个最高频任务排开，形成 maxCount - 1 个长度为 n + 1 的槽段（每段开头放一个最高频任务，后面 n 个位置留给别的任务或待命），最后再补上末尾那一批。

答案只由两个量决定：最高频次 maxCount，以及有多少种任务同为最高频——中间不够塞就待命，够塞则总任务数本身就是答案。

按最高频任务搭框架

公式是 max((maxCount - 1) * (n + 1) + same, total)，其中 same 是频次等于 maxCount 的任务种数，total 是任务总数。两种情形各对应一边：

框架宽松（其他任务不多）：前 maxCount - 1 段每段恰好 n + 1 个单位，塞不满就待命；最后一排只剩那 same 种最高频任务各一个，所以加 same。
任务太多塞爆框架：每段被挤宽到超过 n + 1，但此时任何两个同类任务的间隔都自然大于 n，不需要任何待命，答案就是 total。

public int leastInterval(char[] tasks, int n) {
    int[] cnt = new int[26];
    for (char t : tasks) {
        cnt[t - 'A']++;
    }
    int maxCount = 0, same = 0;
    for (int c : cnt) {
        if (c > maxCount) {
            maxCount = c;
            same = 1;
        } else if (c == maxCount) {
            same++; // 与最高频同频的任务种数
        }
    }
    return Math.max((maxCount - 1) * (n + 1) + same, tasks.length);
}

def leastInterval(tasks: List[str], n: int) -> int:
    cnt = Counter(tasks)
    max_count = max(cnt.values())
    same = sum(1 for c in cnt.values() if c == max_count)  # 与最高频同频的任务种数
    return max((max_count - 1) * (n + 1) + same, len(tasks))

func leastInterval(tasks []byte, n int) int {
    cnt := [26]int{}
    for _, t := range tasks {
        cnt[t-'A']++
    }
    maxCount, same := 0, 0
    for _, c := range cnt {
        if c > maxCount {
            maxCount, same = c, 1
        } else if c == maxCount {
            same++ // 与最高频同频的任务种数
        }
    }
    return max((maxCount-1)*(n+1)+same, len(tasks))
}

pub fn least_interval(tasks: Vec<char>, n: i32) -> i32 {
    let mut cnt = [0i32; 26];
    for t in tasks.iter() {
        cnt[(*t as u8 - b'A') as usize] += 1;
    }
    let max_count = *cnt.iter().max().unwrap();
    let same = cnt.iter().filter(|&&c| c == max_count).count() as i32; // 与最高频同频的任务种数
    ((max_count - 1) * (n + 1) + same).max(tasks.len() as i32)
}

为什么框架总能塞下、不会出现“中途某类任务违反间隔”的情况？填充时按频次从高到低、一列一列地竖着填，同一种任务落在相邻两段的相同列上，间隔恰好 n + 1 - 1 = n，满足要求；频次更低的任务更稀疏，只会间隔更大。最容易忽略的是 same 的含义——它数的是种数不是次数，且必须包含最高频任务自己（所以 same 至少为 1）；漏掉与 maxCount 同频的其他任务，末尾那一排就会少算。

复杂度

指标	复杂度	原因
时间	`O(m)`	m 为任务总数，统计频次一遍即可
空间	`O(1)`	计数数组固定 26 个格子

可以迁移的模式

带间隔约束的调度问题，先找“出现最多的元素”，它决定了时间轴的下界；
结果分“资源稀疏需要空转”和“资源充足自然满足”两种情形时，往往可以各推一个式子再取 max，绕开逐步模拟；
数学公式解之外，这题也能用大顶堆按频次模拟逐轮取任务，但当公式能直接证明下界可达时，模拟就是多余的。

“找瓶颈、算下界、证明下界可达”是贪心构造题的通用三步，这题是把三步都压缩进一行公式的典型。