调试LeetCode《Process Tasks Using Servers》问题：代码部分测试用例失败

题目说明 #

给定两个0索引整数数组servers和tasks，长度分别为n和m。servers[i]表示第i台服务器的权重，tasks[j]表示处理第j个任务所需的秒数。

任务通过任务队列分配给服务器：

• 初始状态下所有服务器空闲，队列为空。
• 在第j秒，第j个任务被插入队列（第0个任务在第0秒插入）。
• 只要存在空闲服务器且队列非空，队列头部的任务会被分配给权重最小的空闲服务器；若权重相同，则分配给索引最小的服务器。
• 若没有空闲服务器且队列非空，则等待直到有服务器空闲，立即分配下一个任务。若多台服务器同时空闲，则按任务插入顺序，遵循上述权重和索引优先级分配多个任务。
• 在第t秒被分配任务j的服务器，会在t + tasks[j]秒时恢复空闲。

需要构建长度为m的数组ans，其中ans[j]为第j个任务被分配到的服务器索引，最终返回该数组。

问题与代码 #

我写的Java代码在部分测试用例上失败，但找不到问题所在，以下是我的代码：

class Solution {
    public int[] assignTasks(int[] servers, int[] tasks) {

        if(servers.length >= 34 ){
                System.out.println(" 22 "+servers[22]+" 34 "+servers[34]);
        }
        
      
       
    // Server Priority Queue
    // 0 -> server
    // 1 -> server index
    PriorityQueue<List<Integer>> freeServer = new PriorityQueue<>(
            (a,b) -> {
              if(a.get(0) == b.get(0)){
                return a.get(1) - b.get(1);
              }else{
                return a.get(0) - b.get(0);
              }
            }
    );

    // Create array list of servers with index
    for(int i=0;i<servers.length;i++){
      List<Integer> list = new ArrayList<>();
      list.add(servers[i]);
      list.add(i);
      freeServer.add(list);
    }


    // List<List<Integer>> usedServer = new ArrayList<>();

    // 0 -> server
    // 1 -> server index
    // 2 -> time
    // Unavailable usedServer       
    PriorityQueue<List<Integer>> usedServer = new PriorityQueue<>(
            (a,b) -> a.get(2) - b.get(2)
    );

    int time = 0;

    int[] res = new int[tasks.length];


    for(int i=0;i<tasks.length;i++){
      time = Math.max(time, i);


    if(freeServer.size() == 0){
         time = usedServer.peek().get(2);
    }
    
      
      while(usedServer.size() > 0 && usedServer.peek().get(2) <= time){

        List<Integer> list = usedServer.poll();

        if( list.get(1) == 22 && usedServer.size() > 0){
            System.out.println("---------"+usedServer.peek().get(1));
        }
        List<Integer> newList = new ArrayList<>();
        newList.add(list.get(0));
        newList.add(list.get(1));
        freeServer.add(newList);

      }

      if(freeServer.size() != 0){
           List<Integer> list = freeServer.poll();
            // index 2 is time
            List<Integer> newList = new ArrayList<>();
            newList.add(list.get(0));
        newList.add(list.get(1));
             newList.add(tasks[i]+time);
             usedServer.add(newList);
            res[i] =newList.get(1);
            
      }

    }


    return res;
    
    }
}

代码问题分析与修复 #

你的代码存在关键逻辑漏洞：当freeServer为空时，仅将time设置为最早可用服务器的时间，但未处理同一时间点多台服务器同时恢复空闲的情况，导致部分服务器未被及时放回空闲队列，进而引发任务分配错误。

另外，使用List<Integer>存储服务器信息易引发索引访问错误，且代码可读性较差，建议改用自定义类封装服务器数据。

修复后的代码示例 #

class Solution {
    static class Server {
        int weight;
        int index;
        int freeTime;

        Server(int weight, int index) {
            this.weight = weight;
            this.index = index;
            this.freeTime = 0;
        }
    }

    public int[] assignTasks(int[] servers, int[] tasks) {
        // 空闲服务器队列：按权重升序，权重相同按索引升序
        PriorityQueue<Server> freeServers = new PriorityQueue<>((a, b) -> {
            if (a.weight == b.weight) {
                return a.index - b.index;
            }
            return a.weight - b.weight;
        });

        // 忙碌服务器队列：按空闲时间升序
        PriorityQueue<Server> busyServers = new PriorityQueue<>((a, b) -> a.freeTime - b.freeTime);

        // 初始化空闲服务器队列
        for (int i = 0; i < servers.length; i++) {
            freeServers.add(new Server(servers[i], i));
        }

        int[] res = new int[tasks.length];
        int time = 0;

        for (int i = 0; i < tasks.length; i++) {
            time = Math.max(time, i);

            // 将所有已到空闲时间的服务器移回空闲队列
            while (!busyServers.isEmpty() && busyServers.peek().freeTime <= time) {
                freeServers.add(busyServers.poll());
            }

            // 如果没有空闲服务器，跳转到最早的空闲时间，并再次同步所有空闲服务器
            if (freeServers.isEmpty()) {
                time = busyServers.peek().freeTime;
                while (!busyServers.isEmpty() && busyServers.peek().freeTime <= time) {
                    freeServers.add(busyServers.poll());
                }
            }

            // 分配任务
            Server server = freeServers.poll();
            res[i] = server.index;
            server.freeTime = time + tasks[i];
            busyServers.add(server);
        }

        return res;
    }
}

修复说明 #

1. 自定义Server类封装服务器权重、索引和空闲时间，避免List索引错误，提升代码可读性。
2. 当freeServers为空时，更新time后再次执行循环，确保同一时间点恢复的所有服务器都被移回空闲队列。
3. 简化逻辑流程，每次分配任务前确保所有可恢复的服务器都已回到空闲队列，避免任务分配遗漏。

内容的提问来源于stack exchange，提问作者harry