P235. 任务调度

leetcode 621 lintcode 945 贪心 队列 讨论

温馨提示:您没有权限查看当前视频。 立即购买观看视频

描述

这个题目说的是,给你一个字符数组和一个非负整数 n。字符数组表示等待 CPU 处理的任务,每个任务用 A 到 Z 中的一个字符表示,并且每个任务都可以在一个时间单位内完成;n 表示冷却时间,即相同任务之间需要间隔至少 n 个时间单位才能再次执行,冷却时间内的每个时间单位,可以选择执行不同的任务或是让 CPU 处于闲置状态。

现在你要重新组织任务的执行顺序,并计算出最少需要多少个时间单位才能完成所有任务。

比如说,给你的任务数组是:

A, A, A, B, B, B, D

给你的冷却时间是:

n = 2

完成所有任务最少需要 8 个时间单位,一种执行序列是:

A, B, D, A, B, _, A, B

序列中的 '_' 表示 CPU 处于闲置状态。

因此,对于这个例子,你要返回 8。

关于 AlgoCasts

AlgoCasts 旨在用心做好每一个算法讲解视频。每个视频包含两个部分:题目的剖析讲解以及编码,力求在讲解清楚到位的基础上,尽可能地保持视频精简短小,让大家可以在碎片时间里进行学习,并收获这些算法题背后的思想与乐趣。