想系统提升编程能力、查看更完整的学习路线欢迎访问 AI Compasshttps://github.com/tingaicompass/AI-Compass仓库持续更新刷题题解、Python 基础和 AI 实战内容适合想高效进阶的你。 第100课:任务调度器模块:堆与优先队列 |难度:Medium ⭐⭐LeetCode 链接:https://leetcode.cn/problems/task-scheduler/前置知识:第97课(前K个高频元素)、Counter、贪心思想预计学习时间:30分钟 题目描述给定一个由若干任务组成的数组,每个任务用大写字母A-Z表示。每个任务可以在1个单位时间内完成,但相同任务之间必须间隔至少n个单位时间(称为冷却时间)。你可以按任意顺序执行任务,但必须在空闲时等待以满足冷却要求。问完成所有任务至少需要多少个单位时间?示例:输入:tasks [A,A,A,B,B,B], n 2 输出:8 解释:执行顺序可以是 A - B - idle - A - B - idle - A - B 时间间隔为 2,总共需要 8 个单位时间约束条件:1 tasks.length 10^4tasks[i] 是大写英文字母0 n 100 边界用例(面试必考)用例类型输入期望输出考察点无冷却tasks[“A”,“A”,“A”], n03冷却时间为0,无需等待单任务tasks[“A”], n21只有一个任务,无冷却高频任务tasks[“A”,“A”,“A”,“A”,“A”,“A”,“B”,“C”,“D”], n216最高频任务主导总时间任务种类多tasks[“A”,“B”,“C”,“D”,“E”,“F”,“G”], n17任务种类足够,无需空闲最大规模len(tasks)10000, n100—性能边界 思路引导生活化比喻想象你是一名厨师,需要做3道菜:红烧肉(A)、炒青菜(B)、煲汤©。问题是:每做完一道红烧肉后,锅必须冷却2分钟才能再做下一道红烧肉(冷却时间n2)。笨办法:傻傻等待。做完A1 → 等2分钟 → 做A2 → 等2分钟 → 做A3,中间什么都不干。浪费时间!聪明办法:充分利用冷却时间!做完A1 → 插入做B → 插入做C → 再做A2 → 插入做B → 插入做C → 再做A3。这样冷却时间都被利用了,没有空闲。关键洞察:如果A太多(比如有10个A),而B、C很少,那即使穿插也不够填满所有冷却间隙,最终还是得等待。关键洞察出现次数最多的任务决定了整体时间的下限!其他任务尽量填充在最高频任务之间的冷却间隙中。 解题思维链Step 1:理解题目 → 锁定输入输出输入:任务列表 tasks(字符数组),冷却时间 n(整数)输出:完成所有任务的最小总时间(整数)限制:相同任务之间必须间隔至少n个时间单位Step 2:先想笨办法(暴力模拟)可以用队列模拟整个执行过程:维护一个优先队列(堆),每次取出频率最高的任务执行,执行后放入冷却队列,等n个时间单位后再放回堆。时间复杂度:O(total_time * log k),其中total_time可能非常大瓶颈在哪:需要逐个时间单位模拟,效率低Step 3:瓶颈分析 → 优化方向模拟的瓶颈在于逐个时间单位推进。能不能直接计算出最终时间?核心问题:总时间由什么决定?优化思路:数学公式直接计算,利用最高频任务的特性Step 4:选择武器选用:数学公式 贪心思想(最优解)或堆 模拟(直观解)理由:数学公式能直接算出答案,O(n)时间堆模拟能展示算法思路,适合面试讲解模式识别提示:当题目涉及冷却时间、“间隔安排”,优先考虑贪心 数学公式 解法一:堆 模拟(直观解)思路用最大堆维护任务频率,每次取频率最高的min(k1个任务)执行(kn1是一个周期),执行后更新频率,重新放回堆。统计总时间。图解过程示例:tasks [A,A,A,B,B,B], n 2 初始频率:A:3, B:3 最大堆:[3,3] 周期1(长度3): 取A(频率3) → 执行A → 频率变2 取B(频率3) → 执行B → 频率变2 取C(无) → 空闲idle 执行序列:A B idle 更新堆:[2,2] 时间:3 周期2(长度3): 取A(频率2) → 执行A → 频率变1 取B(频率2) → 执行B → 频率变1 取C(无) → 空闲idle 执行序列:A B idle 更新堆:[1,1] 时间:336 周期3(长度2): 取A(频率1) → 执行A → 频率变0 取B(频率1) → 执行B → 频率变0 执行序列:A B 更新堆:[] 时间:628 总时间:8Python代码fromtypingimportListfromcollectionsimportCounterimportheapqdefleastInterval_heap(tasks:List[str],n:int)-int: 解法一:堆 模拟 思路:用最大堆每次贪心选择频率最高的任务 ifn0:returnlen(tasks)# 统计每个任务的频率freqCounter(tasks)# 最大堆(用负数模拟)max_heap[-countforcountinfreq.values()]heapq.heapify(max_heap)total_time0whilemax_heap:# 一个周期可以执行 n1 个任务cycle[]for_inrange(n1):ifmax_heap:cycle.append(-heapq.heappop(max_heap))# 执行后更新频率forcountincycle:ifcount-10:heapq.heappush(max_heap,-(count-1))# 如果堆空了,说明是最后一个周期,只需实际任务数# 否则需要完整周期长度(可能有idle)total_timelen(cycle)ifnotmax_heapelsen1returntotal_time# ✅ 测试print(leastInterval_heap([A,A,A,B,B,B],2))# 期望输出:8print(leastInterval_heap([A,A,A,A,A,A,B,C,D,E,F,G],2))# 期望输出:16print(leastInterval_heap([A,B,C,D],1))# 期望输出:4复杂度分析时间复杂度(total_time * log k) — k为任务种类数(最多26),total_time为最终时间具体地说:如果有1000个任务,可能需要模拟1000多个时间单位,每次堆操作O(log 26)空间复杂度(k) — 堆的大小,最多26种任务优缺点✅ 思路直观,容易理解执行过程✅ 适合面试时先讲解算法思路❌ 时间复杂度较高,有更优的数学解法 解法二:数学公式(最优解)优化思路通过数学分析,我们发现:最高频任务的频率max_freq决定了最少需要多少个框架周期每个周期之间需要n个间隔其他任务尽量填充到这些间隔中关键公式:设最高频任务频率为 max_freq,出现max_freq次的任务有 max_count 个 最少时间 (max_freq - 1) * (n 1) max_count 但是,如果任务总数len(tasks)比这个公式大,说明任务足够多,不需要空闲,直接返回len(tasks)关键想法:最高频任务之间形成骨架,其他任务填充血肉,如果血肉不够才需要idle图解过程示例1:tasks [A,A,A,B,B,B], n 2 统计频率: A:3, B:3 max_freq 3 max_count 2(A和B都是3次) 可视化骨架: A _ _ A _ _ A ↓ A B _ A B _ A B 公式:(3-1) * (21) 2 2*3 2 8 总时间:max(8, 6) 8 示例2:tasks [A,A,A,B,C,D,E,F], n 2 统计频率: A:3, 其他都是1 max_freq 3 max_count 1 可视化骨架: A _ _ A _ _ A ↓ A B C A D E A F 公式:(3-1) * (21) 1 2*3 1 7 实际任务数:8 总时间:max(7, 8) 8(任务足够多,无需空闲)Python代码defleastInterval(tasks:List[str],n:int)-int: 解法二:数学公式(最优解) 思路:最高频任务决定骨架,其他任务填充间隙 ifn0:returnlen(tasks)# 统计每个任务的频率freqCounter(tasks)# 找出最高频率max_freqmax(freq.values())# 统计有多少个任务达到最高频率max_countsum(1forcountinfreq.values()ifcountmax_freq)# 公式计算最少时间min_time(max_freq-1)*(n1)max_count# 如果任务总数更多,说明不需要空闲returnmax(min_time,len(tasks))# ✅ 测试print(leastInterval([A,A,A,B,B,B],2))# 期望输出:8print(leastInterval([A,A,A,A,A,A,B,C,D,E,F,G],2))# 期望输出:16print(leastInterval([A,B,C,D],1))# 期望输出:4print(leastInterval([A,A,A],0))# 期望输出:3复杂度分析时间复杂度(m) — m为任务总数,只需遍历一次统计频率具体地说:如果有10000个任务,只需O(10000)一次遍历,远快于模拟空间复杂度(k) — k为任务种类数,最多26为什么是最优解✅ 时间O(m)已经达到理论最优(至少要统计所有任务)✅ 空间O(1)常数级(最多26种任务)✅ 代码简洁,面试中容易写对✅ 通过数学公式直接计算,无需模拟 Pythonic 写法利用 Counter 的 most_common() 方法简化:defleastInterval_pythonic(tasks:List[str],n:int)-int:Pythonic写法:利用most_common()freqCounter(tasks)max_freqfreq.most_common(1)[0][1]# 最高频率max_countsum(1forfinfreq.values()iffmax_freq)returnmax((max_freq-1)*(n1)max_count,len(tasks))⚠️面试建议:先写清晰版本展示思路,再提 Pythonic 写法展示语言功底。面试官更看重你的数学推导过程,而非代码行数。 解法对比维度解法一:堆模拟 解法二:数学公式(最优)时间复杂度O(total_time * log k)O(m)← 时间最优空间复杂度O(k)O(k)代码难度中等简单(关键在推导)面试推荐⭐⭐⭐⭐⭐← 首选适用场景展示算法思路面试首选,效率最高为什么数学公式是最优解:时间O(m)已经是理论最优(必须至少看一遍所有任务)避免了逐个时间单位的模拟,直接数学计算代码量少,不容易出错面试建议:先用1分钟口述堆模拟的思路(表明你理解贪心策略)立即切换到最优解:数学公式法重点讲解公式推导:“最高频任务形成骨架,其他任务填充间隙”手绘示意图帮助面试官理解强调为什么这是最优:时间O(m)已达理论下限 面试现场模拟面试中的完整对话流程,帮你练习边想边说。面试官:请你解决一下这道任务调度器问题。你:(审题30秒)好的,这道题要求在冷却时间约束下完成所有任务,求最少总时间。让我先想一下…我的第一个想法是用堆模拟:每次贪心选择频率最高的任务执行,维护冷却队列。时间复杂度是O(total_time * log k)。不过我们可以用数学公式优化到O(m),核心思路是:最高频任务决定骨架,其他任务填充间隙。公式是(max_freq - 1) * (n 1) max_count,再和任务总数取最大值。面试官:很好,请写一下数学公式的代码。你:(边写边说)# 第一步:统计频率freqCounter(tasks)# 第二步:找最高频率和达到最高频率的任务数max_freqmax(freq.values())max_countsum(1forfinfreq.values()iffmax_freq)# 第三步:套公式min_time(max_freq-1)*(n1)max_count# 第四步:和任务总数取最大(处理任务很多的情况)returnmax(min_time,len(tasks))面试官:为什么是这个公式?你:(画图解释)比如tasks[“A”,“A”,“A”,“B”,“B”,“B”], n2。A出现3次,是最高频。我可以这样排列:A _ _ A _ _ A这形成了一个骨架,有(max_freq-1)个间隙,每个间隙长度n1。最后还要加上最后一个周期的max_count个任务。所以是(3-1)*(21)28。如果其他任务足够多,比如有10个不同任务,那直接执行就行,不需要空闲,所以要取max(公式值, 任务总数)。面试官:测试一下?你:用示例[“A”,“A”,“A”,“B”,“B”,“B”], n2:(3-1)*328 ✓边界:[“A”], n2:max((1-1)*31, 1)1 ✓无冷却:[“A”,“A”], n0:max((2-1)*11, 2)2 ✓高频追问追问应答策略“为什么公式中要-1再max_count?”“因为最高频任务形成的周期是max_freq-1个间隙,最后一个周期不需要完整的n1长度,只需要max_count个任务即可”“如果有多个任务都是最高频怎么办?”“公式中的max_count就是处理这个情况的,它统计了达到最高频的任务数,这些任务都会出现在每个周期的末尾”“空间能更优吗?”“已经是O(k)常数空间了(最多26种任务),无法进一步优化”“实际工程中怎么用?”“类似CPU任务调度、多核处理器的任务分配,都需要考虑冷却时间或依赖关系” 知识点总结Python技巧卡片 # 技巧1:Counter统计频率 — 字典子类,专门用于计数fromcollectionsimportCounter freqCounter([A,A,B])# Counter({A: 2, B: 1})# 技巧2:most_common() — 获取频率最高的元素freq.most_common(1)# [(A, 2)]max_freqfreq.most_common(1)[0][1]# 技巧3:堆模拟最大堆 — Python只有最小堆,用负数模拟最大堆importheapq max_heap[-3,-2,-1]heapq.heapify(max_heap)# 最大元素3在堆顶 底层原理(选读)为什么Python的heapq只有最小堆?Python的设计哲学是一个问题只有一个明显的解决方法。最小堆已经足够,需要最大堆时只需对所有值取负数即可。这样避免了重复实现,保持标准库简洁。Counter的底层实现:Counter继承自dict,内部就是普通字典。most_common()方法实际上是对字典进行排序,时间复杂度O(k log k),k为元素种类数。算法模式卡片 模式名称:贪心 数学公式适用条件:当问题涉及间隔安排、“冷却时间”、周期调度时识别关键词:“冷却”、“间隔”、“相同任务不能连续”模板代码:deftask_scheduler_pattern(tasks,n):# 1. 统计频率freqCounter(tasks)# 2. 找最高频及其数量max_freqmax(freq.values())max_countsum(1forfinfreq.values()iffmax_freq)# 3. 套公式min_time(max_freq-1)*(n1)max_count# 4. 取最大值(处理任务充足的情况)returnmax(min_time,len(tasks))易错点 ⚠️忘记处理n0的情况:冷却时间为0时,直接返回任务总数公式中忘记-1:是(max_freq-1)*(n1),不是max_freq*(n1),因为最后一个周期不需要完整长度忘记max_count:多个任务达到最高频时,最后一个周期需要max_count个位置,不是1个忘记取max:当任务种类很多时,可能不需要空闲,要取max(公式值, 任务总数)️ 工程实战(选读)这个算法思想在真实项目中的应用,让你知道学了有什么用。场景1:多核CPU任务调度。现代CPU需要避免同一类型密集计算连续执行导致过热,通过插入其他类型任务实现冷却。场景2:网络请求限流。对同一IP的请求设置冷却时间,避免DDoS攻击。类似本题的相同任务间隔n。场景3:游戏技能冷却。MOBA游戏中技能释放后需要冷却,类似任务调度问题。️ 举一反三完成本课后,试试这些同类题目来巩固知识:题目难度相关知识点提示LeetCode 767. 重构字符串Medium贪心堆类似任务调度,要求相邻字符不同LeetCode 358. K距离间隔重排字符串Hard贪心堆任务调度的升级版LeetCode 1481. 不同整数的最少数目Medium贪心堆频率统计贪心选择 课后小测试试这道变体题,不要看答案,自己先想5分钟!题目:给定任务数组和冷却时间n,要求返回最优执行顺序的字符串(包括idle),而不是时间长度。比如tasks[“A”,“A”,“A”,“B”,“B”],n2,返回AB_AB_A(其中_表示idle)。 提示(实在想不出来再点开)仍然基于最高频任务的骨架,用堆维护剩余任务,每个周期贪心取频率最高的n1个任务。✅ 参考答案deftaskSchedulerOrder(tasks:List[str],n:int)-str:返回执行顺序字符串ifn0:return.join(tasks)freqCounter(tasks)max_heap[(-count,char)forchar,countinfreq.items()]heapq.heapify(max_heap)result[]whilemax_heap:cycle[]for_inrange(n1):ifmax_heap:count,charheapq.heappop(max_heap)cycle.append((count,char))result.append(char)elifmax_heap:# 还有任务但当前周期不够result.append(_)# 添加空闲forcount,charincycle:ifcount10:# 还有剩余(-count 1)heapq.heappush(max_heap,(count1,char))return.join(result)核心思路:用堆模拟,每次取频率最高的任务,不足n1个时补充_表示空闲。如果这篇内容对你有帮助推荐收藏 AI Compasshttps://github.com/tingaicompass/AI-Compass更多系统化题解、编程基础和 AI 学习资料都在这里后续复习和拓展会更省时间。