华为OD机试之打印机队列（Java源码）

打印机队列

题目描述

输入描述

输出描述

用例

源码和解析
解析：

示例代码方式一：

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class T35 {
	static class Task {
		int num;
		int priority;
		int taskId;

		public Task(int num, int priority, boolean isFinished,
				int taskId) {
			super();

			this.num = num;
			this.priority = priority;
			this.taskId = taskId;
		}

		@Override
		public String toString() {
			return "Task [num=" + num + ", priority=" + priority
					+ ", taskId=" + taskId + "]\n";
		}
	}

	// 按输入的设备编号进行分堆 存放在不同的map中 键是打印机编号 值为该打印机的任务信息
	static Map<Integer, List<Task>> taskMap = new HashMap<Integer, List<Task>>();
	static List<Integer> pList = new ArrayList<>();// 记录设备的id集
													// 后面就不用keyset去遍历map了
	static boolean isOrdered = false;

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int num = scanner.nextInt();
		int id = 0;
		for (int i = 0; i < num; i++) {
			id++;
			String op = scanner.next();
			int p = scanner.nextInt();
			int priority = 0;
			if (op.equals("IN")) {
				priority = scanner.nextInt();
			}
			if (!taskMap.containsKey(p)) {
				List<Task> tasks = new ArrayList<T35.Task>();
				taskMap.put(p, tasks);
				pList.add(p);
			}
			Task task = new Task(p, priority, false, id);
			if (op.equals("IN")) {
				taskMap.get(p).add(task);
				isOrdered = false;
			} else {
				if (!isOrdered)
					sort();
				List<Task> tasksItem = taskMap.get(p);
				Task t = tasksItem.size() == 0 ? null : tasksItem.get(0);
				if (t != null) {
					tasksItem.remove(0);
				}
				System.out.println((t == null ? "NULL" : t.taskId));
			}
		}
	}

	// 排序
	public static void sort() {
		isOrdered = true;
		for (int p : pList) {
			taskMap.get(p).sort(new Comparator<Task>() {
				@Override
				public int compare(Task o1, Task o2) {
					// 优先级降序 高的排前面 方便取值
					if (o1.priority > o2.priority) {
						return -1;
					} else if (o1.priority < o2.priority) {
						return 1;
					}
					// 优先级一样 任务顺序排序
					if (o1.taskId < o2.taskId) {
						return -1;
					} else if (o1.taskId > o2.taskId) {
						return 1;
					}
					return 0;
				}
			});
		}
	}
}

执行示意图如下：


大根堆解法
解析

源码示例 大根堆

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class T35 {
	static class Task {
		int devId; // 设备编号
		int priority;
		int taskId;
		boolean isFinished;
		Task leftTask; // 左节点
		Task rightTask; // 右节点
		Task parenTask;// 父节点

		@Override
		public String toString() {
			return "Task [devId=" + devId + ", priority=" + priority
					+ ", taskId=" + taskId + "]\n";
		}
	}

	// 按输入的设备编号进行分堆 存放在不同的map中 键是打印机编号 值为该打印机的任务信息
	static Map<Integer, Task> taskMap = new HashMap<Integer, Task>();
	static Task objTask = null;

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int num = scanner.nextInt();
		int id = 0;
		for (int i = 0; i < num; i++) {
			id++;
			String op = scanner.next();
			int devId = scanner.nextInt();
			int priority = 0;
			if (op.equals("IN")) {
				priority = scanner.nextInt();
			}
			Task task = new Task();
			task.devId = devId;
			task.priority = priority;
			task.taskId = id;
			if (op.equals("IN")) {
				if (!taskMap.containsKey(devId)) {
					taskMap.put(devId, task);
					System.out.println("挂载跟节点：" + task.taskId);
				} else {
					// 挂载节点
					handle(devId, task);
				}
			} else {
				// 出节点
				objTask = null;
				find(taskMap.get(devId));
				if (objTask == null)
					System.out.println("NULL");
			}
		}
	}

	// 找到目标设备要出的那个
	public static void find(Task task) {
		if (task.isFinished == false) {
			// 自己未完成 那么可能到右侧
			if (task.rightTask != null && task.rightTask.isFinished == false) {
				find(task.rightTask);// 找右侧子节点 这种是不可能找左侧子节点的
			} else {
				// 到自己
				task.isFinished = true;
				objTask = task;
				System.out.println(task.taskId);// 输出任务id
			}
		} else {
			// 当前已完成 那么只有可能是其左侧节点
			if (task.leftTask != null)
				find(task.leftTask);
		}
	}

	public static void handle(int devId, Task task) {
		Task rootTask = taskMap.get(devId);
		mount(rootTask, task);
	}

	// 遍历节点 进行挂载
	public static void mount(Task task, Task objTask) {
		if (task.priority < objTask.priority) {
			// 挂载右侧
			if (task.rightTask != null) {
				mount(task.rightTask, objTask);
			} else {
				task.rightTask = objTask;
				System.out.println("节点" + objTask.taskId + "挂载在节点"
						+ task.taskId + "右侧");
			}
		} else {
			// 挂载左侧
			if (task.leftTask != null) {
				mount(task.leftTask, objTask);
			} else {
				task.leftTask = objTask;
				System.out.println("节点" + objTask.taskId + "挂载节点" + task.taskId
						+ "左侧");
			}
		}
	}
}

大根堆代码运行示意图：