笔试刷题-头条(转载)2018-06-27
2018-06-27 本文已影响0人
Dodo159753
转载连接:
https://blog.csdn.net/qq_23666815/article/details/79182805
题目描述:
产品经理(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实现的时间点。
思路如下:
就是题目给出逻辑模拟加优先队列选择即可
很肉的一个题目转载一下别人吧
转载代码如下:
import java.util.*;
public class Main{
private static Scanner sc = new Scanner(System.in);
static class IdeaTask {
int pmSeq;
int raiseTime;
int prio;
int timeCost;
int endTime;
public IdeaTask(int pmSeq, int raiseTime, int prio, int timeCost) {
this.pmSeq = pmSeq;
this.raiseTime = raiseTime;
this.prio = prio;
this.timeCost = timeCost;
}
}
static class PM {
PriorityQueue<IdeaTask> pq = new PriorityQueue<>(Comparator.comparingInt(x -> x.raiseTime));
//给定程序员开始工作的时间,找到这个PM最想完成的任务
IdeaTask mostDesiredTask(int startTime) {
PriorityQueue<IdeaTask> pq2 = new PriorityQueue<>((x, y) -> {
if (x.prio != y.prio) return y.prio - x.prio;
else {
if (x.timeCost != y.timeCost) return x.timeCost - y.timeCost;
else return x.raiseTime - y.raiseTime;
}
});
while (pq.peek() != null && pq.peek().raiseTime <= startTime) {
pq2.offer(pq.poll());
}
IdeaTask mostDesiredTask = (pq2.isEmpty()) ? pq.poll() : pq2.poll();
while (!pq2.isEmpty()) {
pq.offer(pq2.poll());
}
return mostDesiredTask;
}
}
static class Programmer {
int nextWorkTime;//下次可以工作的时间
public Programmer(int nextWorkTime) {
this.nextWorkTime = nextWorkTime;
}
}
//从多个PM 最想要完成的Idea中,选其中的一个PM想要完成的idea
private static IdeaTask selectTask(PM[] pms, int workTime) {
PriorityQueue<IdeaTask> pq = new PriorityQueue<>((x, y) -> {
if (x.raiseTime == y.raiseTime || (x.raiseTime <= workTime && y.raiseTime <= workTime)) {
if (x.timeCost != y.timeCost) return x.timeCost - y.timeCost;
else return x.pmSeq - y.pmSeq;
}
if (x.raiseTime > workTime && y.raiseTime > workTime) return x.raiseTime - y.raiseTime;
if (x.raiseTime > workTime) return 1;
if (y.raiseTime > workTime) return -1;
return 0;
});
for (int i = 1; i < pms.length; i++) {
PM pm = pms[i];
IdeaTask desiredTask = pm.mostDesiredTask(workTime);
if (desiredTask != null)
pq.offer(desiredTask);
}
IdeaTask task = pq.poll();
while (!pq.isEmpty()) {
IdeaTask tmp = pq.poll();
pms[tmp.pmSeq].pq.offer(tmp);
}
return task;
}
private static List<IdeaTask> getTasks(int taskNum) {
List<IdeaTask> tasks = new LinkedList<>();
while (taskNum-- > 0) {
tasks.add(new IdeaTask(sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt()));
}
return tasks;
}
private static PM[] initPM(int n, List<IdeaTask> tasks) {
PM[] pms = new PM[n + 1];
for (int i = 1; i <= n; i++) pms[i] = new PM();
for (IdeaTask task : tasks) {
pms[task.pmSeq].pq.offer(task);
}
return pms;
}
public static void main(String[] args) {
int n = sc.nextInt(), m = sc.nextInt(), p = sc.nextInt();
List<IdeaTask> tasks = getTasks(p);
PM[] pms = initPM(n, tasks);
PriorityQueue<Programmer> losersPq = new PriorityQueue<>(Comparator.comparingInt(x -> x.nextWorkTime));
for (int i = 0; i < m; i++) losersPq.offer(new Programmer(0));
while (true) {
Programmer loser = losersPq.poll();
IdeaTask task = selectTask(pms, loser.nextWorkTime);
if (task == null) break;
task.endTime = Integer.max(task.raiseTime, loser.nextWorkTime) + task.timeCost;
loser.nextWorkTime = task.endTime;
losersPq.offer(loser);
}
for (IdeaTask task : tasks) {
System.out.println(task.endTime);
}
}
}