本文主要是介绍牛客网 字节跳动算法题-任务调度，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

描述

产品经理(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序号、提出时间、优先等级和所需时间。

所有输入数据范围为 [1, 3000]

输出描述：

输出P行，分别表示每个idea实现的时间点。

题解：

生产者消费者问题的状态模拟：我们需要将输入的任务根据提出时间加入生产者队列（使用优先队列，按照提出时间先后排序）。随着时间K的改变，判断消费者（程序员）的状态和任务状态，将任务加到待办事项队列中（此队列也使用优先队列，根据题意对设计自定义排序），具体看待发注释。

import java.util.*;
public class Main {
    //创建Idea类
    static class Idea {
        int id;//记录任务序号，于PM编号无关
        int time;//记录任务提出时间
        int order;//记录任务优先级
        int spendTime;//记录任务花费时间
        int finish;//记录任务完成时间，初始化默认为-1
        public Idea(int id,int time,int order,int spendTime) {
            this.id = id;
            this.time = time;
            this.order = order;
            this.spendTime = spendTime;
            this.finish = -1;
        }
    }
    public static void main (String []args){
        Scanner scanner = new Scanner(System.in);
        String[] str = scanner.nextLine().split(" ");
        int N = Integer.parseInt(str[0]),M = Integer.parseInt(str[1]),P = Integer.parseInt(str[2]);
        
        //记录程序员的任务剩余工作时间
        int[] programer = new int [M];
        //记录每个任务
        HashMap<Integer, Idea> map = new HashMap<>();
        //生产线 //按照提出时间排序
        PriorityQueue<Idea> createQ = new PriorityQueue<>(Comparator.comparingInt(o -> o.time));
        //待完成任务 //按照优先级order->花费时间spendTime->提出时间time排序
        PriorityQueue<Idea> taskQ = new PriorityQueue<>(new Comparator<Idea>() {
            @Override public int compare(Idea o1, Idea o2){
                if(o1.order > o2.order){
                    return 1;
                }else if(o1.order < o2.order){
                    return -1;
                }else{
                    if(o1.spendTime > o2.spendTime){
                        return 1;
                    }else if(o1.spendTime < o2.spendTime){
                        return -1;
                    }else{
                        if(o1.time > o2.time){
                            return 1;
                        }else if(o1.time < o2.time){
                            return -1;
                        }else{
                            return 0;
                        }
                    }
                }
            }
        });
        //初始化生产者队列
        for(int i = 0; i < P; i++) {
            String[] temp = scanner.nextLine().split(" ");
            Idea idea = new Idea(i,Integer.parseInt(temp[1]),Integer.parseInt(temp[2]),Integer.parseInt(temp[3]));
            map.put(i, idea);
            createQ.add(idea);
        }
        //两个Queue都是空时，停止
        int k = 0;
        while ((!taskQ.isEmpty()) || (!createQ.isEmpty())) {
            while ((!createQ.isEmpty()) && createQ.peek().time == k) {
                taskQ.offer(createQ.poll());
            }
            int indexProgramer = 0;//遍历每一个程序员
            while (indexProgramer < programer.length) {
                if(programer[indexProgramer] > 0){
                    programer[indexProgramer]--; //程序员干活啦
                    indexProgramer++;
                }else{//这个程序员空闲
                    if(taskQ.isEmpty()){
                        indexProgramer++;
                    }else{//有任务做了
                        Idea idea = taskQ.poll();
                        idea.finish = k + idea.spendTime;//计算完成时间
                        programer[indexProgramer] = idea.spendTime;//程序员需要消耗的时间
                    }
                }
            }
            k++;//时间增加
        }
        for(int i = 0; i < P; i++){
            System.out.println(map.get(i).finish);
        }
    }
}

这篇关于牛客网 字节跳动算法题-任务调度的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！