【华为OD题库-111】模拟工作队列-Java

题目

让我们来模拟一个工作队列的运作，有一个任务提交者和若干任务执行者，执行者从1开始编号
提交者会在给定的时刻向工作队列提交任务，任务有执行所需的时间，
执行者取出任务的时刻加上执行时间即为任务完成的时刻
执行者完成任务变为空闲的时刻会从工作队列中取最老的任务执行，若这一时刻有多个空闲的执行者，其中优先级最高的会执行这个任务。
编号小的执行者优先级高。初始状态下所有执行者都空闲。
工作队列有最大长度限制，当工作队列满而有新的任务需要加入队列时，队列中最老的任务会被丢弃。
特别的，在工作队列满的情况下，当执行者变为空闲的时刻和新的任务提交的时刻相同时，队列中最老的任务被取出执行，新的任务加入队列。
输入描述:
输入为两行。
第一行为2N个正整数，代表提交者提交的N个任务的时刻和执行时间。
第一个数字是第一个任务的提交时刻，第二个数字是第一个任务的执行时间，以此类推。用例保证提交时刻不会重复，任务按提交时刻升序排列。
第二行为两个数字，分别为工作队列的最大长度和执行者的数量。
两行的数字都由空格分隔。N不超过20，数字为不超过1000的正整数
输出描述:
输出两个数字，分别为最后一个任务执行完成的时刻和被丢弃的任务的数量，数字由空格分隔。
示例1:
输入:
1 3 2 2 3 3
3 2
输出:
7 0
示例2:
输入:
1 6 2 4 4 3 6 3
1 2
输出:
10 0
示例3:
输入∶
1 6 2 4 3 3 4 3 6 3
1 2
输出:
10 1

思路

可以使用对列模拟排队的对列
任务完成时间等于任务开始时间+任务执行时间，开始时间不等同任务进入的时间，因为有可能在排队。可以使用优先级队列存放任务，让任务结束时间在前的始终排在前面，那么该队列的队首元素就是第一个被执行完成的任务，任务执行完，需要出队（工作对列）
如果当前有空余的执行器，并且排队的对列不为空，那么工作对列加入排队队列的队首元素，并且设置任务开始时间为当前时间
如果当前时间等于任务进入的时间，那么判断当前是否有空余的执行器数量，若有，则直接执行（设置开始时间为当前时间）；否则加入排队的队列中（不设置开始时间）
在加入排队队列时，如果排队队列长度超过限制，那么丢弃队首元素，丢弃数+1
最后返回结果即可

题解

package hwod;

import java.util.*;

public class SimulationWorkQueue {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int workMaxSize = sc.nextInt(), excuteNum = sc.nextInt();
        int[] res = simulationWorkQueue(nums, workMaxSize, excuteNum);
        System.out.println(res[0] + " " + res[1]);
    }

    private static int[] simulationWorkQueue(int[] nums, int workMaxSize, int excuteNum) {
        int time = 0, discarded = 0;
        LinkedList<Task> queue = new LinkedList<>();//排队的对列
        PriorityQueue<Task> work = new PriorityQueue<>();//工作对列
        boolean isFirst = true;
        int curSize = 0;//当前执行者数量
        int k = 0;//取nums第几个元素？
        while (isFirst || !queue.isEmpty() || !work.isEmpty()) {
            isFirst = false;
            time++;
            if (!work.isEmpty() && work.peek().getEndTime() == time) {
                //执行完成，出队
                work.poll();
                curSize--;
            }
            while (curSize < excuteNum && !queue.isEmpty()) {
                //先从对列取任务执行
                Task task = queue.removeFirst();
                task.setStartTime(time);
                work.add(task);
                curSize++;
            }
            if (k < nums.length / 2 && time == nums[2 * k]) {
                //新任务加入对列
                if (curSize < excuteNum) {
                    //直接执行
                    work.add(new Task(nums[2 * k], time, nums[2 * k + 1]));
                    curSize++;
                } else {
                    //排队
                    if (queue.size() == workMaxSize) {
                        queue.removeFirst();
                        discarded++;
                    }
                    queue.addLast(new Task(nums[2 * k], nums[2 * k + 1]));
                }
                k++;
            }
        }
        return new int[]{time, discarded};
    }
}

class Task implements Comparable<Task> {
    private int id;
    private int entryTime;
    private int startTime;
    private int endTime;
    private int excuteTime;

    public Task(int entryTime, int excuteTime) {
        this.entryTime = entryTime;
        this.excuteTime = excuteTime;
    }

    public Task(int entryTime, int startTime, int excuteTime) {
        this.entryTime = entryTime;
        this.startTime = startTime;
        this.excuteTime = excuteTime;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public int getEntryTime() {
        return entryTime;
    }

    public void setEntryTime(int entryTime) {
        this.entryTime = entryTime;
    }

    public int getStartTime() {
        return startTime;
    }

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

    public int getEndTime() {
        return startTime + excuteTime;
    }

    public void setEndTime(int endTime) {
        this.endTime = endTime;
    }

    public int getExcuteTime() {
        return excuteTime;
    }

    public void setExcuteTime(int excuteTime) {
        this.excuteTime = excuteTime;
    }

    @Override
    public int compareTo(Task o) {
        return this.getEndTime() - o.getEndTime();
    }
}

推荐

如果你对本系列的其他题目感兴趣，可以参考华为OD机试真题及题解（JAVA），查看当前专栏更新的所有题目。

说明

本专栏所有文章均为原创，欢迎转载，请注明文章出处：https://blog.csdn.net/qq_31076523/article/details/134176793。百度和各类采集站皆不可信，搜索请谨慎鉴别。技术类文章一般都有时效性，本人习惯不定期对自己的博文进行修正和更新，因此请访问出处以查看本文的最新版本。