今日头条2018笔试编程题-第三题 任务调度

import java.util.*;
import java.lang.*;

/*
input
2 2 5
1 1 1 2
1 2 1 1
1 3 2 2
2 1 1 2
2 3 5 5
output
3
4
5
3
9
*/
public class toutiaoC {

	public static void solution(int numPM, int numProgramer, int numTask, Task[] tasks) {
		//任务状态：新建->就绪->执行
		
		Queue<Task> BornPQ = new PriorityQueue<Task>(numTask, new BornComparator()); //新建队列
		Queue<Task> ReadyPQ = new PriorityQueue<Task>(numTask, new ReadyComparator()); //就绪队列
		Queue<Task> RunningPQ = new PriorityQueue<Task>(numProgramer, new RunningComparator()); //运行队列
		int[] retFinishTimes = new int [numTask];


		//init BornPQ
		for (int i = 0; i < numTask; i++) {
			BornPQ.offer( tasks[i] );
		}

		//init RunningPQ
		for (int i = 0; i < numProgramer && i < numTask; i++) {
			Task curTask = BornPQ.poll();
			// curTask.startTime = curTask.bornTime;
			// curTask.finishTime = curTask.startTime + curTask.taskTime;
			curTask.setStartTime(curTask.bornTime);
			RunningPQ.offer(curTask);
		}

		while( !RunningPQ.isEmpty() ) {
			Task finishTask = RunningPQ.poll();
			int curTime = finishTask.finishTime;
			retFinishTimes[finishTask.index] = curTime;

			//update BornPQ and ReadyPQ: BornPQ.poll -> ReadyPQ.offer;
			//update BornPQ and ReadyPQ: ReadypQ.poll -> RunningPQ.offer;
			while( !BornPQ.isEmpty() && BornPQ.peek().bornTime <= curTime ) {
				ReadyPQ.offer( BornPQ.poll() );
			}
			while( RunningPQ.size() < numProgramer && !ReadyPQ.isEmpty() ) {
				Task runningTask = ReadyPQ.poll();
				// runningTask.startTime = curTime;
				// runningTask.finishTime = runningTask.startTime + runningTask.taskTime;
				runningTask.setStartTime(curTime);
				RunningPQ.offer(runningTask);
			}
		}

		//result
		for (int i = 0; i < numTask; i++) {
			System.out.println( retFinishTimes[i] );
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int numPM = sc.nextInt();
		int numProgramer = sc.nextInt();
		int numTask = sc.nextInt();
		Task[] tasks = new Task[numTask];
		for (int i = 0; i < numTask; i++) {
			int PMId = sc.nextInt();
			int bornTime = sc.nextInt();
			int priority = sc.nextInt();
			int taskTime = sc.nextInt();
			tasks[i] = new Task(i, PMId, bornTime, priority, taskTime);
		}

		solution(numPM, numProgramer, numTask, tasks);
	}
}

//新建状态
class BornComparator implements Comparator<Task> {
	//bornTime 递增 @Override public int compare(Task o1, Task o2) {
		return o1.bornTime - o2.bornTime;
	}
}

//就绪状态
class ReadyComparator implements Comparator<Task> {
	//priority -> taskTime -> bornTime -> PMId @Override public int compare(Task o1, Task o2) {
		if (o1.priority != o2.priority) {
			return o1.priority - o2.priority;
		}
		else if ( o1.taskTime != o2.taskTime ) {
			return o1.taskTime - o2.taskTime;
		}
		else if ( o1.bornTime != o2.bornTime ) {
			return o1.bornTime - o2.bornTime;
		}
		else {
			return o1.PMId - o2.PMId;
		}
	}
}

//运行状态
class RunningComparator implements Comparator<Task> {
	//finishTime 递增 @Override public int compare(Task o1, Task o2) {
		return o1.finishTime - o2.finishTime;
	}
}


class Task {
	public int index;
	public int PMId;
	public int bornTime;
	public int priority;
	public int taskTime;

	public int startTime;
	public int finishTime;

	public Task(int index, int PMId, int bornTime, int priority, int taskTime) {
		this.index = index;
		this.PMId = PMId;
		this.bornTime = bornTime;
		this.priority = priority;
		this.taskTime = taskTime;
	}

	public void setStartTime(int startTime) {
		this.startTime = startTime;
		this.finishTime = this.startTime + this.taskTime;
	}
}