Idea 的实现时间

Tag: 笔试算法题 Posted on 2022-03-16 20:28:58 Edited on 2022-03-16 21:35:22 Views: 140

概述

https://www.nowcoder.com/questionTerminal/e86766d02c1342ed8380f4e171f360f2

产品经理(PM)有很多好的idea,而这些idea需要程序员实现。现在有N个PM,在某个时间会想出一个 idea,每个 idea 有提出时间、所需时间和优先等级。对于一个PM来说,最想实现的idea首先考虑优先等级高的,相同的情况下优先所需时间最小的,还相同的情况下选择最早想出的,没有 PM 会在同一时刻提出两个 idea。

同时有M个程序员,每个程序员空闲的时候就会查看每个PM尚未执行并且最想完成的一个idea,然后从中挑选出所需时间最小的一个idea独立实现,如果所需时间相同则选择PM序号最小的。直到完成了idea才会重复上述操作。如果有多个同时处于空闲状态的程序员,那么他们会依次进行查看idea的操作。

求每个idea实现的时间。

输入第一行三个数N、M、P,分别表示有N个PM,M个程序员,P个idea。随后有P行,每行有4个数字,分别是PM序号、提出时间、优先等级和所需时间。输出P行,分别表示每个idea实现的时间点。

模拟法

首先对所有 idea 按时间排序,为每个 PM 的 idea 维护一个优先级队列(优先级定义按照 PM 的偏好,初始时为空)。

开始模拟时间的进行,每次循环:

  1. 遍历已按时间升序排序的 idea 列表,遍历到 idea 的出现时间大于当前时间为止,把新出现的 idea 放入对应的 PM 的优先级队列里。
  2. 遍历所有 PM 的优先级队列的队首,使用一个新的优先级队列(优先级定义按照程序员的偏好)记录所有 PM 的最优先的 idea。
  3. 遍历所有程序员,更新其剩余工作时间,如果其没工作了,就分配第二步中优先级队列中的最优先 idea 给他,同时更新对应 PM 的 优先级队列,并记录结束时间,更新该程序员的剩余工作时间。
  4. 最后更新时间:递增 1。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/