算法:什么是任务计划问题?

255 阅读1分钟

在这里插入图片描述

最近小多米喜欢做各种各样的任务计划,但是这么多任务在一起,她就头大不知道该先做哪个?也不知道怎么才能以最短的时间完成这些任务?

为了帮助小多米解决这个问题,今天我门就来看看算法领域的“任务计划”问题。

“任务计划”问题规则如下: 给定一个字符串,表示CPU需要执行的任务。 这个字符串由大写字母A到Z构成,不同的字母代表不同的任务。完成任务不需要按照给定的顺序。 每项任务都可以在一个单位时间内被完成。 在每个单位时间,CPU可以选择完成一个任务或是不工作。

但是,会有一个非负的冷却时间“n”,表示在执行两个“相同的任务”之间,必须至少有n个单位时间,此时CPU不能执行该任务,只能执行其他任务或者不工作。

小多米需要计算CPU完成所有给定任务所需的最少单位时间数?

样例1如下:

输入: tasks = ['A','A','A','B','B','B'], n = 2
输出: 8
解释:
A -> B -> idle -> A -> B -> idle -> A -> B.

样例2如下:

输入: tasks = ['A','A','A','B','B','B'], n = 1
输出: 6
解释:
A -> B -> A -> B -> A -> B.

上面就是算法中“任务计划”问题。聪明的你,知道怎么帮助小多米解决这个问题吗?