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;
}
}
I have inserted triplets using Pair class in the priority queue and one pair is polled from the queue two times and was inserted only once. How it could be possible? I am also attaching the console output for print statements I added to debug. Highlighted the unusual behavior.
The output of Code: (Note the behavior in output. Highlighting it (3,0,0) polled twice?)
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
The question was from a recent Leetcode Contest that was over now. Link to the discussion section of the question. Link to question Link to IDE run
It is not entirely clear, but I think your problem is caused by an incorrect implementation of 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;
This returns p.b and as a side-effect it assigns p.b to this.b. This is completely wrong.
It is possible that you mean return this.b - p.b;
Note that since your compareTo method is changing one of the Pair objects, the results are going to be messed up. That's probably why some of the Pair objects appear to be returned more than once. (In fact, they are different Pair objects ... but you have mutated them so that they have the same values in the c field.)
The expression this.c - p.c gives an incorrect answer in edge cases. For example, this.c is very large and p.c is negative, then the subtraction may overflow to a negative number which says that this.c is "less" than p.c ... which it isn't.
See Java Integer compareTo() - why use comparison vs. subtraction? for a more on this.
Here are a couple of correct ways to compare two int values to give a result that is compatible with the compareTo contract:
Longhand:
if (this.c == p.c) {
return 0;
} else if (this.c < p.c) {
return -1;
} else {
return +1;
}
Using conditional expressions:
return (this.c == p.c) ? 0 : ((this.c < p.c) ? -1 : +1);
Using Integer.compare
return Integer.compare(this.c, p.c);
If we assume that the Pair objects are supposed to be immutable, then this is a correct1 implementation:
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);
}
}
}
Q: Why declare the fields as final ?
A: To prevent accidental changes to the fields, within the Pair class itself and also by other classes to which the class and its fields are accessible.
Q: Why use if ... else?
A: Because it is clearer. And because the JIT compiler should generate equivalent (optimal) code in either case.
Q: What about compare? Won't the method call be inefficient?
A: Probably not. The method call will probably be inlined by the JIT compiler.
Q: Does efficiency matter at all?
A: In your example it is irrelevant. In the general case, it is probably irrelevant2.
1 - The class name Pair is also incorrect. It should be Triple.
2 - You should only try to hand optimize this after you have 1) benchmarked your code, 2) profiled it, and 3) determined that the compareTo method is really a performance hotspot.