【每日算法Day 99】优先级任务队列的实际执行顺序

题目描述

输入一个整数数组，数组中的数字依次代表了任务队列中任务的优先级，这些任务按照初始顺序编号为0，1，2，...，n - 1。每次取出队列头部的任务i，如果队列中没有优先级更高的任务则直接执行，如果有优先级更高的则直接拿出优先级最高的任务执行，并把编号为i的任务放入队列尾部。请给出队列中的任务实际执行的顺序。

示例

输入：[2,2,5,3]
输出：[2,3,0,1]
解释：原数组中的任务的编号分别为0，1，2，3。首先拿出第一个任务优先级为2，由于队列中存在优先级更大的任务5则拿出5执行，则第一个执行的任务编号为2
    把编号为0的任务放入队列尾部。接下来以此类推，最终执行的任务编号顺序为2，3，0，1。

解题思路

首先想到的可能是统计并排序队列中所有的优先级，根据排序后的优先级从大到小再扫描队列中的任务并把对应优先级的任务顺序记下来。这样的方法需要O(nlogn)的时间和O(n)的空间来同时保存任务的编号信息。

为了排序使用O(nlogn)的时间，可以使用单调队列来得到当前队列中的最大值。将数组中的元素填入主队列和单调队列都只需要O(n)的时间。之后每次从主队列拿出头部任务，如果任务已经执行过（使用HashSet标记）则丢弃；如果没有执行过且单调队列头的任务优先级更大，则将当前任务插入主队列尾部并将单调队列的头元素出队列作为要执行的任务；如果没有执行过且单调队列头的任务优先级不大于当前任务，则直接执行当前任务。

public class JobQueue {
    public static void main(String[] args) {
        JobQueue jobQueue = new JobQueue();
        System.out.println(Arrays.toString(jobQueue.jobSchedule(new int[]{2,2,5,3})));
    }

    private int[] jobSchedule(int[] jobs) {
        //单调队列
        Deque<JobIndex> monoQueue = new LinkedList<>();
        //主队列
        Queue<JobIndex> sequence = new LinkedList<>();
        //哈希集合，用于标记特定编号的任务是否已经执行
        HashSet<Integer> set = new HashSet<>();
        int n = jobs.length;
        int[] result = new int[n];
        int resultIndex = 0;

        //填充单调队列
        for (int i = 0; i < n; i++) {
            while (!monoQueue.isEmpty()&& monoQueue.peekLast().jobPriority<jobs[i])
                    monoQueue.pollLast();
            monoQueue.offerLast(new JobIndex(jobs[i], i));
        }

        //填充主队列
        for (int i = 0; i < jobs.length; i++) {
            sequence.offer(new JobIndex(jobs[i], i));
        }

        while (!sequence.isEmpty()) {
            JobIndex jobIndex = sequence.poll();
            //单调队列非空且主队列头部任务的优先级小于单调队列头部任务的优先级，就从单调队列出任务，并把主队列这次的头任务入队尾
            if (!monoQueue.isEmpty() && jobIndex.jobPriority < monoQueue.peekFirst().jobPriority) {
                sequence.offer(jobIndex);
                JobIndex max = monoQueue.pollFirst();
                result[resultIndex++] = max.index;
                //从单调队列出的任务并没有直接从主队列中出队列，所以需要标记一下
                set.add(max.index);
            } else {//否则只要主队列当前的头部任务没有执行过，就正常执行
                if (!set.contains(jobIndex.index)) {
                    if (resultIndex<n)
                        result[resultIndex++] = jobIndex.index;
                    monoQueue.pollFirst();
                }
            }
        }
        return result;
    }

    private static class JobIndex {
        int jobPriority;
        int index;

        public JobIndex(int jobPriority, int index) {
            this.jobPriority = jobPriority;
            this.index = index;
        }
    }
}