意外行为java优先级队列。对象添加了一次但轮询了两次。怎么可能呢？

Question

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Solution solution = new Solution();
        int[] res = solution.assignTasks(new int[]{3,3,2}, new int[]{1,2,3,2,1,2});
    }
}
class Solution {
    public int[] assignTasks(int[] servers, int[] tasks) {
        PriorityQueue<Pair> free = new PriorityQueue(); // (wt, id, time)
        PriorityQueue<Pair> busy = new PriorityQueue(); // (time, wt, id)
        
        for (int i = 0; i < servers.length; i++) {
            free.add(new Pair(servers[i], i, 0));
            System.out.println("Free Added " + i + " " + servers[i] + " " + i + " " + 0 + " " + free.size());
        }
        
        int[] ans = new int[tasks.length];
        for (int i = 0; i < tasks.length; i++) {
            Pair b = busy.peek();
            while (b != null && b.a <= i) {
                busy.poll();
                System.out.println("Busy Polled " + i + " " + b.a + " " + b.b + " " + b.c + " " + busy.size());
                free.add(new Pair(b.b, b.c, b.a));
                System.out.println("Free Added " + i + " " + b.b + " " + b.c + " " + b.a + " " + free.size());
                b = busy.peek();
            }
            Pair p = free.poll();
            
            int wt = p.a;
            int id = p.b;
            
            // int time = p.c;
            System.out.println("Free Polled " + i + " " + p.a + " " + p.b + " " + p.c + " " + free.size());
            
            ans[i] = id;
            busy.add(new Pair(i + tasks[i], wt, id));
            System.out.println("Added to Busy " + i + " " + (i + tasks[i]) + " " + p.a + " " + p.b + " " + busy.size());
        }
        
        return ans;
    }
}
class Pair implements Comparable<Pair> {
    int a, b, c;
    Pair(int x, int y, int z) {
        a = x;
        b = y;
        c = z;
    }
    public int compareTo(Pair p) {
         if (this.a == p.a) {
             if (this.b == p.b) return this.c - p.c;
             return this.b = p.b;
         }
         return this.a - p.a;
     }
    
}

代码的输出：（注意输出中的行为。突出显示它（3,0,0）轮询了两次？）

Free Added 0 3 0 0 1       (Added to the queue)
Free Added 1 3 1 0 2
Free Added 2 2 2 0 3
Free Polled 0 2 2 0 2
Added to Busy 0 1 2 2 1
Busy Polled 1 1 2 2 0
Free Added 1 2 2 1 3
Free Polled 1 2 2 1 2
Added to Busy 1 3 2 2 1
Free Polled 2 3 0 0 1     (Polled 1st time)
Added to Busy 2 5 3 0 2
Busy Polled 3 3 2 2 1
Free Added 3 2 2 3 2
Free Polled 3 2 2 3 1
Added to Busy 3 5 2 2 2
Free Polled 4 3 0 0 0     (Polled 2nd time)
Added to Busy 4 5 3 0 3
Busy Polled 5 5 3 0 2
Free Added 5 3 0 5 1
Busy Polled 5 5 3 0 1
Free Added 5 3 0 5 2
Busy Polled 5 5 3 2 0
Free Added 5 3 2 5 3
Free Polled 5 3 0 5 2
Added to Busy 5 7 3 0 1

这个问题来自最近的一次Leetcode竞赛，现在已经结束了。链接到问题的讨论部分。链接到问题链接到IDE运行

Answer 1

这并不完全清楚，但我认为您的问题是由compareTo的一个不正确的实现引起的。

public int compareTo(Pair p) {
     if (this.a == p.a) {
         if (this.b == p.b) return this.c - p.c;
         return this.b = p.b;
     }
     return this.a - p.a;
 }

return this.b = p.b;

这将返回p.b，作为一个副作用，它将p.b分配给This.b。这是完全错误的。

您的意思可能是返回这个。b-p.b；

参见Java整数compareTo（）-为什么使用比较vs.减法？更多关于这个的。

以下是比较两个int值以获得与compareTo协定兼容的结果的几种正确方法：

>

长：

if (this.c == p.c) {
    return 0;
} else if (this.c < p.c) {
    return -1;
} else {
    return +1;
}

return (this.c == p.c) ? 0 : ((this.c < p.c) ? -1 : +1);

return Integer.compare(this.c, p.c);

class Pair implements Comparable<Pair> {
    final int a, b, c;

    Pair(int x, int y, int z) {
        a = x;
        b = y;
        c = z;
    }

    public int compareTo(Pair p) {
        if (this.a == p.a) {
            if (this.b == p.b) {
                return Integer.compare(this.c, p.c);
            } else {
                return Integer.compare(this.b, p.b);
            }
        } else {
            return Integer.compare(this.a, p.a);
        }
    }
}

问：为什么使用if...else？
A:因为它更清晰。并且因为JIT编译器在这两种情况下都应该生成等价的（最佳）代码。

问:比较怎么样？方法调用不会效率低吗？
A:可能不会。方法调用可能由JIT编译器内联。

问：效率到底重要吗？
A:在你的例子中，它是无关紧要的。在一般情况下，它很可能是无关紧要的²。