1882.使用服务器处理任务

题目

给你两个下标从 0 开始的整数数组 servers 和 tasks ，长度分别为 n 和 m 。servers[i] 是第 i 台服务器的权重，而 tasks[j] 是处理第 j 项任务所需要的时间（单位：秒）。

你正在运行一个仿真系统，在处理完所有任务后，该系统将会关闭。每台服务器只能同时处理一项任务。第 0 项任务在第 0 秒可以开始处理，相应地，第 j 项任务在第 j 秒可以开始处理。处理第 j 项任务时，你需要为它分配一台权重最小的空闲服务器。如果存在多台相同权重的空闲服务器，请选择下标最小的服务器。如果一台空闲服务器在第 t 秒分配到第 j 项任务，那么在 t + tasks[j] 时它将恢复空闲状态。

如果没有空闲服务器，则必须等待，直到出现一台空闲服务器，并尽可能早地处理剩余任务。如果有多项任务等待分配，则按照下标递增的顺序完成分配。

如果同一时刻存在多台空闲服务器，可以同时将多项任务分别分配给它们。

构建长度为 m 的答案数组 ans ，其中 ans[j] 是第 j 项任务分配的服务器的下标。

返回答案数组 ans 。

示例

示例 1：输入：servers = [3,3,2], tasks = [1,2,3,2,1,2]输出：[2,2,0,2,1,2]解释：事件按时间顺序如下：- 0 秒时，第 0 项任务加入到任务队列，使用第 2 台服务器处理到 1 秒。- 1 秒时，第 2 台服务器空闲，第 1 项任务加入到任务队列，使用第 2 台服务器处理到 3 秒。- 2 秒时，第 2 项任务加入到任务队列，使用第 0 台服务器处理到 5 秒。- 3 秒时，第 2 台服务器空闲，第 3 项任务加入到任务队列，使用第 2 台服务器处理到 5 秒。- 4 秒时，第 4 项任务加入到任务队列，使用第 1 台服务器处理到 5 秒。- 5 秒时，所有服务器都空闲，第 5 项任务加入到任务队列，使用第 2 台服务器处理到 7 秒。

题解

在这里插入图片描述

代码详解

class Solution {    public int[] assignTasks(int[] servers, int[] tasks) {        //开始解题        //busy二维数组，优先队列满足队首服务器t最小,相同的话id最小，（正在执行的任务什么时候结束，下标）        PriorityQueue
   
     busy=new PriorityQueue<>(new Comparator
    
     () {            @Override            public int compare(int[] o1, int[] o2) {                if(o1[0]==o2[0])                    return o1[1]-o2[1];                else                    return o1[0]-o2[0];            }        });        //idle二维数组 （空闲的服务器），队列满足对首的服务器权重最小，权重相同的话，按照id最小的排序（服务器的优先级，下标）        PriorityQueue
     
       idle=new PriorityQueue<>(new Comparator
      
       () {            @Override            public int compare(int[] o1, int[] o2) {                if(o1[0]==o2[0])                    return o1[1]-o2[1];                else                    return o1[0]-o2[0];            }        });        //初始化可以先将所有的服务器放到空闲队列种        for (int i = 0; i < servers.length; i++) {            idle.add(new int[]{servers[i],i});        }        //设置一个时间戳来记录当前的时间，初始值为0        int ts=0;        //设置一个数组来存放，结果        int[] ans=new int[tasks.length];        for (int i = 0; i < tasks.length; i++) {            ts=Math.max(i,ts);            //while循环确保，任务是按照顺序执行的，不会出现后面的任务跑到前面的情况            while(true){                updateServerStatus(servers,idle,busy,ts);                if(idle.isEmpty()){                    //空闲服务器队列是空的，就直接将ts设置为下一个服务器的空闲时间                    ts=busy.peek()[0];                }else{                    int [] usedserver=idle.poll();                    busy.add(new int[]{ts+tasks[i],usedserver[1]});                    ans[i]=usedserver[1];                    break;                }            }        }        return ans;    }    //更新服务器的状态    private static void updateServerStatus(int[] servers, PriorityQueue
       
         idle, PriorityQueue
        
          busy, int ts) { while (!busy.isEmpty()){ int[] busyserver=busy.peek(); if(busyserver[0]<=ts){ //任务执行完成，添加到空闲服务器种去 busy.poll(); //将执行完的服务器的（权重、下标）存到idel中去 idle.add(new int[]{servers[busyserver[1]],busyserver[1]}); }else{ //否则在这一时间服务器不用更新 break; } } }}

转载地址：http://mtgji.baihongyu.com/

你可能感兴趣的文章