题意

给定一个数组代表一组任务，每个下标代表任务的id，里面的每一项都是一个长度为2的数组，分别表示一个任务的等待时间，以及处理任务需要的时间。只有一个CPU来处理这些任务，处理任务遵守的原则：

• 没有任务的时候CPU则等待
• 有可用的任务，cpu选择处理任务需要时间最短的。如果有多个任务的处理时间都是相通的，选择id最小的。
• cpu一次只可以处理一个任务
• cpu只有处理完当前任务才可以处理下一个任务

返回任务的处理顺序

思路

这道理要考虑使用堆，这题思路就是，先将任务按照任务的等待时间从小到大排列。

然后将到当前时间所有可以被cpu处理的任务放到heap中，heap的调整规则就是，如果任务处理时间相同，按照id来排列，否则就按照任务处理时间排列。然后让heap中的元素弹出，就是最终的处理顺序。

所以整体的逻辑就是

// 1. 任务根据等待时间排序

for 存在任务{
	// 挑选任务，放到heap中
	 pickTaskAndInsertIntoHeap()
	 // 记录任务的处理顺序
   recordTaskId();
}

• 对任务按照等待时间排序

  

  图1

• 开始挑选任务

  定义costTime 记录已经过了多长时间，这个主要用来挑选可以被处理的任务。

  注意costTime的变化方式，因为我们的任务已经按照等待时间进行了排序，所以在判断第N个任务的时候可以能出现：

  • costTime < 第N个任务的等待时间

    这个情况，我们**需要将costTime更新为第N个任务的等待时间**，然后继续挑选可以处理的任务

  • constTime ≥ 第N个任务的等待时间

    这个情况就说，某些任务是可以被处理的，然后把可被处理的任务都放到heap中。

• 记录处理完的任务ID，更新costTime

  当我们在一轮遍历后，挑选出了若干可执行的任务，我们就是将任务从heap中弹出，然后增加我们的costTime。

  我们需要关注任务弹出条件

  • 首先需要heap不为空，
  • 其次就是每弹出一个任务，会增加costTime，我们需要关注，再剩余的任务中是否有等待时间小于costTime的任务，因为很有可能后面的任务满足了等待时间并且有着更短的处理时间。

  这里记录完成后，如果还有任务则重复挑选，记录id的步骤。

这里继续对上述例子进行说明。