Idea 的实现时间
概述
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 的偏好,初始时为空)。
开始模拟时间的进行,每次循环:
- 遍历已按时间升序排序的 idea 列表,遍历到 idea 的出现时间大于当前时间为止,把新出现的 idea 放入对应的 PM 的优先级队列里。
- 遍历所有 PM 的优先级队列的队首,使用一个新的优先级队列(优先级定义按照程序员的偏好)记录所有 PM 的最优先的 idea。
- 遍历所有程序员,更新其剩余工作时间,如果其没工作了,就分配第二步中优先级队列中的最优先 idea 给他,同时更新对应 PM 的 优先级队列,并记录结束时间,更新该程序员的剩余工作时间。
- 最后更新时间:递增 1。
Links: idea-的实现时间